#include <fstream>
#include <cstring>
#include <vector>
#include <set>
#define DIM 50100

using namespace std;

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

int N,M;
vector < pair<int,int> > v[DIM];
set <pair <int,int > > T;
int D[DIM];
int main(){
    fin>>N>>M;
    while(M--){
        int x,y,cost;
        fin>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    memset(D,0x3f3f3f3f,sizeof(D));
    D[1]=0;
    T.insert(make_pair(0,1));
    while(T.size()>0){
        int val=(*T.begin()).first;
        int x=(*T.begin()).second;
        T.erase(*T.begin());
        for(std::vector < pair <int,int> >::iterator it=v[x].begin();it!=v[x].end();it++)
            if(D[it->first]>val+it->second){
                D[it->first]=val+it->second;
                T.insert(make_pair(D[it->first],it->first));
            }
    }
    for(int i=2;i<=N;i++)
        if(D[i]==0x3f3f3f3f)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";
    fin.close();fout.close();
    return 0;
}