#include <fstream>

using namespace std;

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

const long long mare = 999999999999999;
long long n, m, i, j;
long long d[50005];
bool ok;
struct muchie
{
    long long x, y, cost;
}q[250005];

int main()
{
    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> q[i].x >> q[i].y >> q[i].cost;
        if (q[i].x == 1)
            d[q[i].y] = q[i].cost;
    }

    for (i = 2; i <= n; i++)
        if (d[i] == 0)
            d[i] = mare;
    ok = 0;
    while (!ok)
    {
        ok = 1;
        for (i = 1; i <= m; i++)
            if (d[q[i].x] + q[i].cost < d[q[i].y])
                d[q[i].y] = d[q[i].x] + q[i].cost, ok = 0;
    }
    for (i = 2; i <= n; i++)
        if (d[i] != mare)
            g << d[i] << " ";
        else g << "0 ";
    return 0;
}