#include <iostream>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <queue>

#define PII pair<int,int>
#define INF 100000
using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    unordered_map<int,vector<PII>> Map;
    for(int i = 1; i <= m; i ++){
        int a,b,c;
        cin >> a >> b;
        c = pow(2,i - 1);
        Map[a].push_back(make_pair(c,b));
    }
    unordered_map<int,int> dis;
    priority_queue<PII,vector<PII>,greater<PII>> op;
    op.push(make_pair(0,0));
    while(op.size() != 0){
        PII po = op.top();
        op.pop();
        int aa = po.first;
        int bb = po.second;
        if(dis.count(bb) != 0) continue;
        dis[bb] = aa;
        for(auto i : Map[bb]){
            int u = i.first;
            int uu = i.second;
            if(dis.count(uu) == 0){
                op.push(make_pair((u + aa),uu));
            }
        }
    }
    for(int i = 1; i < n; i ++){
        if(dis.count(i) == 0) cout << "wa!" << endl;
        else cout << dis[i] % INF << endl;
    }
    return 0;
}