#include <cstdio>
#include <vector>
#include <queue>
#define nmax 50005
#define pb push_back
#define inf 999999999
using namespace std;

struct dijkstra
{
    int nod, cost;
}e;

vector <dijkstra> a[nmax];
queue <int> q;

int n, m, i, j, x, y, cost, dmin[nmax];

bool viz[nmax];

int main ()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d%d", &n, &m);
    i=1;
    while(m)
    {
        scanf("%d%d%d", &x, &y, &cost);
        e.nod=y;
        e.cost=cost;
        a[x].pb(e);
        dmin[i]=inf;
        --m; ++i;
    }
    int nod;
    vector<dijkstra>::iterator it;

    q.push(1); dmin[1]=0; viz[1]=1;
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        viz[nod]=0;

        for(it=a[nod].begin(); it!=a[nod].end(); ++it)
        {
            e=*it;
            if(dmin[nod]+e.cost<dmin[e.nod])
            {
                dmin[e.nod]=e.cost+dmin[nod];
                if(!viz[e.nod])
                {
                    q.push(e.nod);
                    viz[e.nod]=1;
                }
            }
        }
    }

    for(i=2; i<=n; ++i)
    printf("%d ", (dmin[i]<inf?dmin[i]:0));

    return 0;
}