#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#define mp make_pair
#define pii pair<int,int>
using namespace std;
FILE*in=fopen("dijkstra.in","r");
FILE*out=fopen("dijkstra.out","w");
int noduri,muchii,dist[50001];
priority_queue < pii ,vector< pii >, greater< pii > > q;
vector <pair<int,int> > v[50001];
int main()
{
    fscanf(in,"%d%d",&noduri,&muchii);
    for(int i=2;i<=noduri;++i)
        dist[i]=(1<<30)-1;
    for(int i=1;i<=muchii;++i)
    {
        int data1,data2,data3;
        fscanf(in,"%d%d%d",&data1,&data2,&data3);
        v[data1].push_back(mp(data3,data2));
    }
    q.push(mp(0,1));
    while(!q.empty())
    {
        pair<int,int> curent=q.top();
        q.pop();
        for(int i=0;i<(int)v[curent.second].size();++i)
        {
            if(dist[v[curent.second][i].second]>dist[curent.second]+v[curent.second][i].first)
            {
                dist[v[curent.second][i].second]=dist[curent.second]+v[curent.second][i].first;
                q.push(mp(dist[v[curent.second][i].second],v[curent.second][i].second));
            }
        }
    }
    for(int i=2;i<=noduri;++i)
        if(dist[i])
            fprintf(out,"%d ",dist[i]);
        else
            fprintf(out,"0 ");

fclose(in);
fclose(out);
return 0;
}