#include<fstream>
#include<vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector< pair<int,int> > v[50005] ;
int d[50005],f[50005];
int n,m,i,x,y,z,ok,nod,vecin,minim;
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    for(i=2;i<=n;i++){
        d[i]=2000000000;
    }
    d[1]=0;
    f[1]=1;
    ok=0;
    nod=1;
    while(ok==0){
        for(i=0;i<v[nod].size();i++){
            vecin=v[nod][i].first;
            if(f[vecin]==0){
                d[vecin]=min(d[vecin],d[nod]+v[nod][i].second);
            }
        }
        f[nod]=1;
        minim=2000000000;
        ok=1;
        for(i=1;i<=n;i++){
            if(f[i]==0){
                if(minim>d[i]){
                    minim=d[i];
                    nod=i;
                }
                ok=0;
            }
        }
    }
    for(i=2;i<=n;i++){
        fout<<d[i]<<" ";
    }
    return 0;
}