#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

priority_queue< pair < int ,int > > q;
int n,m,dist[50005];
vector <pair < int ,int > > g[50005];

void citire()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }
    q.push(make_pair(0,1));
}
void dijkstra()
{
    memset(dist,inf,sizeof(dist));
    dist[1]=0;
    while (!q.empty())
    {
        int c=-q.top().first;
        int nod=q.top().second;
        q.pop();

        for (vector <pair <int,int > > :: iterator it=g[nod].begin();it!=g[nod].end();++it)
            if (dist[it->first]>it->second+c)
        {
            dist[it->first]=it->second+c;
            q.push(make_pair(-dist[it->first],it->first));
        }
    }
    for (int i=2;i<=n;++i)
        printf("%d ",dist[i]);
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    return 0;
}