#include <fstream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const unsigned INF=numeric_limits<unsigned>::max()/2;
typedef pair<unsigned, unsigned> pUU;
typedef vector<pUU> vpUU;

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

    unsigned N,M; fin>>N>>M;
    vector<vpUU> graph(N);
    while(M--){
        unsigned A,B,C; fin>>A>>B>>C;
        graph[A-1].push_back(pair<unsigned,unsigned>(C,B-1));
    }

    vector<unsigned> dist(N,INF); dist[0]=0;

    priority_queue<pUU,vpUU,greater<pUU> > Q;
    Q.push(pUU(0,0));

    while(!Q.empty()){
        unsigned cv=Q.top().second;
        unsigned cdist=Q.top().first;
        Q.pop();
        if(cdist<=dist[cv])
            for(vpUU::iterator it=graph[cv].begin();it!=graph[cv].end();++it){
                unsigned v2=it->second, cost=it->first;
                if(dist[v2]>dist[cv]+cost){
                    dist[v2]=dist[cv]+cost;
                    Q.push(pUU(dist[v2],v2));
                }
            }
    }

    for(unsigned i=1;i<N;++i) if(dist[i]==INF) fout<<"0 "; else fout<<dist[i]<<' ';
    fout<<'\n';
}