#include <bits/stdc++.h>
using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int nmax = 50000;
const int mmax = 250000;
const int inf = 0x3f3f3f3f;

vector< vector< pair<int,int> > > dx(nmax+1);
priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > pq;
long long dp[nmax+1];

void dijkstra()
{
    for(int i=1; i<=nmax; i++) dp[i] = inf;
    dp[1] = 0;
    pq.push(make_pair(0,1));
    while(pq.size())
    {
        pair<int,int> now = pq.top();
        pq.pop();
        if(now.first != dp[now.second])
            continue;
        for(int i=0; i<dx[now.second].size(); i++)
        {
            pair<int,int> nxt = dx[now.second][i];
            if(dp[nxt.second] > now.first + nxt.first)
            {
                pq.push(make_pair(now.first + nxt.first, nxt.second));
                dp[nxt.second] = now.first + nxt.first;
            }
        }
    }
}

int main ()
{
    int n,m;
    f >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x,y,cost;
        f >> x >> y >> cost;
        dx[x].push_back(make_pair(cost,y));
    }
    dijkstra();
    for(int i=2; i<=n; i++)
    {
        if(dp[i]!=inf) g << dp[i] << " ";
        else g << "0 ";
    }
    return 0;
}