#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nmax=50000;

struct str{
    int x, y;
};

struct cmp{
    bool operator()(str x,str y){
        return x.y>y.y;
    }
};

priority_queue <str, vector <str>, cmp> h;

vector <str> g[nmax+1];

int d[nmax+1];

str mp(int x,int y){
    str sol;
    sol.x=x;
    sol.y=y;
    return sol;
}

int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        fin>>x>>y>>z;
        g[x].push_back(mp(y,z));
    }
    h.push(mp(1,1));
    d[1]=1;
    while(h.empty()==0){
        int x=h.top().x;
        int y=h.top().y;
        h.pop();
        if(y==d[x]){
            for(int i=0;i<int(g[x].size());i++){
                int xn=g[x][i].x;
                int yn=g[x][i].y;
                if(d[xn]==0||d[x]+yn<d[xn]){
                    d[xn]=d[x]+yn;
                    h.push(mp(xn,d[xn]));
                }
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(d[i]>0){
            fout<<d[i]-1<<" ";
        }else{
            fout<<0<<" ";
        }
    }
    fout<<"\n";
    return 0;
}