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

int n,m,x,y,c,dist[50015];

vector <pair <int ,int > >v[50015];

priority_queue< pair <int, int > > q;

void citire()
{
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)
        dist[i]=10000000;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(make_pair(y,c));
    }
    q.push(make_pair(0,1));
}
void dijkstra()
{
    while(!q.empty())
    {
        y=q.top().second;
        c=-q.top().first;
        q.pop();
        for(vector <pair <int ,int> >::iterator it=v[y].begin();it!=v[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]==10000000)
        printf("0 ");
    else
        printf("%d ",dist[i]);
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    return 0;
}