#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 50005
#define MAXM 250001
#define infinit 10000000
vector< pair<int, int> > g[MAXN];
int n, m;
int d[MAXN], viz[MAXN];
priority_queue< pair<int, int> > pq;
void dijkstra(int s)
{
    int i, x, minim;
    for (i = 1; i <= n + 1; ++i)
        d[i] = infinit;
    d[s] = 0;
    pq.push(make_pair(d[s], s));
    while (!pq.empty())
    {
        x = pq.top().second;
        pq.pop();
        viz[x] = 1;
        for (i = 0; i < g[x].size(); ++i)
        {
            if (d[g[x][i].first] > d[x] + g[x][i].second)
                d[g[x][i].first] = d[x] + g[x][i].second;
            pq.push(make_pair(-d[g[x][i].first], g[x][i].first));
        }
        while (!pq.empty() && viz[pq.top().second])
            pq.pop();
    }
}
int main()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    int i, a, b, c;
    for (i = 0; i < m; ++i)
    {
        f>>a>>b>>c;
        g[a].push_back(make_pair(b, c));
    }
    dijkstra(1);
    ofstream ff("dijkstra.out");
    for (i = 2; i <=n ; ++i)
        if (d[i] != infinit) ff<<d[i]<<' ';
            else ff<<"0 ";
}