///bellman - ford
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>


using namespace std;

vector<pair<int,int> > lv[50100];

queue<int> q;
vector<pair<int,int> >::iterator ii;

int d[50100],is_in_q[50100];

int N,M;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);

    for(int i=1;i<=N;i++)
        d[i] = 200000;

    for(int i=1; i<=M; i++)
    {
        int x,y,cost;
        scanf("%d%d%d",&x,&y,&cost);
        lv[x].push_back(make_pair(y,cost));
    }
    d[1]=0;
    q.push(1);
    is_in_q[1]=1;
    while(!q.empty())
    {
        int x = q.front();
        is_in_q[x]=0;
        q.pop();
        for(ii = lv[x].begin(); ii!=lv[x].end();ii++)
            if(d[x]+ii->second < d[ii->first])
            {
                d[ii->first] = d[x]+ii->second;
                if(!is_in_q[ii->first])
                {
                q.push(ii->first);
                is_in_q[ii->first] = 1;
                }
            }
    }
    for(int i=2;i<=N;i++)
        printf("%d ",d[i]<200000?d[i]:0);

    return 0;
}