#ifndef $
#define $

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

typedef vector< pair <int, int> >::iterator IT;
const int NMAX = 50000, INF = 0b01111111111111111111111111111111;
int n,m;
int d[NMAX];

vector < pair<int,int> > T[NMAX + 1];
queue <int> c;
int bentvan[NMAX + 1];

int main()
{
    ifstream be("dijkstra.in");
    ofstream ki("dijkstra.out");
    be>>n>>m;
    for(int i = 0; i < m; i++)
    {
        int from, to, cost;
        be>>from>>to>>cost;
        T[from].push_back(make_pair(to,cost));
    }

    for(int i = 2; i < n + 1; i++)
        d[i] = INF;
    c.push(1);
    bentvan[1]++;
    while(!c.empty())
    {
        int now = c.front();
        c.pop();
        bentvan[now]--;
        if(bentvan[now] > 0)
            continue;

        for(IT it = T[now].begin(); it != T[now].end(); it++)
        {
            int to = it -> first;
            int cost = it -> second;
            if(d[to] > d[now] + cost)
            {
                d[to] = d[now] + cost;
                c.push(to);
                bentvan[to]++;
            }
        }
    }

    for(int i = 2; i<= n; i++)
    {
        if(d[i] == INF)
            d[i] = 0;
        ki<<d[i]<<" ";
    }

    return 0;
}

#endif