#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define INF 999999999
using namespace std;

const int MAX_NODURI = 50001;
priority_queue <pair<int,int> > pq;
vector <pair<int,int> > G[MAX_NODURI];
int dist[MAX_NODURI];

int main()
{
    FILE *fin, *fout;
    int n,m,i,nod1,nod2,d,nod;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(fin,"%d %d %d",&nod1,&nod2,&d);
        G[nod1].push_back(make_pair(nod2,d));
    }
    for(i=2;i<=n;i++)
        dist[i]=INF;
    pq.push(make_pair(0,1));
    while(!pq.empty()){
        d = pq.top().first;
        nod = pq.top().second;
        pq.pop();
        for(i=0;i<G[nod].size();i++)
            if(dist[G[nod][i].first]>dist[nod]+G[nod][i].second){
                dist[G[nod][i].first]=dist[nod]+G[nod][i].second;
                pq.push(make_pair(dist[G[nod][i].first],G[nod][i].first));
            }
    }
    for(i=2;i<=n;i++)
        if(dist[i]==INF)
            fprintf(fout,"0 ");
        else
            fprintf(fout,"%d ",dist[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}