#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
priority_queue <pair <int, int> > Q;
vector <pair <int, int> > G[10000];
int n,m,dist[200000];
void citire()
{
    int x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        dist[i]=2000000;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d%d",&x,&y,&c);
        G[x].push_back(make_pair(y,c));
    }
    Q.push(make_pair(0,1));
}
void dijkstra()
{
    while(!Q.empty())
   {
       int y=Q.top().second;
    int c=-Q.top().first;
    Q.pop();
    vector <pair <int,int> >::iterator it;
    for(it=G[y].begin();it<G[y].end();it++)
    {
        if(c+it->second<dist[it->first])
            {
                dist[it->first]=c+it->second;
                Q.push(make_pair(-dist[it->first],it->first));
            }
    }
   }
   for(int i=2;i<=n;i++)
    {
        if(dist[i]==2000000)
            printf("0 ");
        else
            printf("%d ",dist[i]);
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    //cout << "Hello world!" << endl;
    return 0;
}