#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
vector<pair<int,int> >f[50005];
const long long inf=1e10;
long long k,i,m,x,j,g[55000],ct;
queue<int>q;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%lld%lld",&x,&m);
    for(k=1;k<=m;k++)
    {
        scanf("%lld%lld%lld",&i,&j,&ct);
        f[i].push_back(make_pair(j,ct));
    }
    /*for(k=1;k<=x;k++)
    {
        for(i=0;i<f[k].size();i++)
            cout<<k<<" "<<f[k][i].first<<" "<<f[k][i].second<<endl;
    }*/
    for(k=2;k<=x;k++)
        g[k]=inf;
    for(q.push(1);!q.empty();)
    {
        k=q.front();
        q.pop();
        for(i=0;i<f[k].size();i++)
        {
            if(g[k]+f[k][i].second<g[f[k][i].first])
            {
                g[f[k][i].first]=g[k]+f[k][i].second;
                q.push(f[k][i].first);
            }
        }
    }
    for(k=2;k<=x;k++)
        printf("%lld ",g[k]);
    return 0;
}