#include <fstream>
#define INF 999999999999

using namespace std;

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

long long n, m, i, j, x, y, c;
struct muchie{
    long long x, y, c;
}G[250002];
long long d[50002];
bool ok;

int main()
{
    f >> n >> m;

    for (i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        G[i].x = x, G[i].y = y, G[i].c = c;
        if (x == 1)
            d[y] = c;
    }
    for (i = 2; i <= n; i++)
        if (d[i] == 0)
            d[i] = INF;

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