#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define MAXN 50005
#define MAXM 250001
#define y first
#define cost second
#define infinit 10000000
vector< pair<int, int> > g[MAXN];
int n, m;
int d[MAXN], viz[MAXN];
void dijkstra(int s)
{
    int i, x, minim;
    for (i = 1; i <= n + 1; ++i)
        d[i] = infinit;
    d[s] = 0;
    //viz[s] = 1;
    x = s;
    int ok = 1;
    while (ok)
    {
        viz[x] = 1;
        ok = 0;
        for (i = 0; i < g[x].size(); ++i)
        {
            if (d[g[x][i].y] > d[x] + g[x][i].cost)
                d[g[x][i].y] = d[x] + g[x][i].cost;
            if (!viz[g[x][i].y]) ok = 1;
        }
        minim = infinit;
        for (i = 1; i <= n; ++i)
            if (d[i] < minim && !viz[i])
            {
                x = i;
                minim = d[i];
            }
    }
}
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\n";
}