#include <fstream>

using namespace std;

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

int mare = 999999999;
int n, m, i, j;
int vec[50005];
bool ok;
struct filip
{
    int x, y, cost;
} v[250005];

int main()
{
    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> v[i].x >> v[i].y >> v[i].cost;
        if (v[i].x == 1)
            vec[v[i].y] = v[i].cost;
    }
    for (i = 2; i <= n; i++)
        if (vec[i] == 0)
            vec[i] = mare;
    ok = 0;
    while (!ok)
    {
        ok = 1;
        for (i = 1; i <= m; i++)
            if (vec[v[i].x] + v[i].cost < vec[v[i].y])
                vec[v[i].y] = vec[v[i].x] + v[i].cost, ok = 0;
    }
    for (i = 2; i <= n; i++)
        if (vec[i] != mare)
            g << vec[i] << " ";
        else
            g << "0 ";
    return 0;
}