#include<fstream>
#include<vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,x,y,c,cost,nod,vecin;
long long minim,q;
long long D[50005],f[50005];
vector < pair <int, int> > v[50003];
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    q=12500000000LL;
    for(i=2;i<=n;i++){
        D[i]=12500000000LL;
    }
    while(f[n]==0){
        minim=12500000000LL;
        for(i=1;i<=n;i++){
            if(D[i]<minim && f[i]==0){
                minim=D[i];
                nod=i;
            }
        }
        f[nod]=1;
        for(vector <pair <int,int > > :: iterator it=v[nod].begin();it!=v[nod].end();it++){
            vecin=it->first;
            cost=it->second;
            if(f[vecin]==0 && D[vecin]>D[nod]+cost){
                D[vecin]=D[nod]+cost;
            }
        }
    }
    for(i=2;i<=n;i++){
        if(D[i]!=q)
            fout<<D[i]<<" ";
        else{
            fout<<"0"<<" ";
        }
    }
    return 0;
}