#include <stdio.h>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;
FILE* f, * g;
struct name
{
    int a, b;
};

class compar
{
public:
    bool operator() (name A, name B)
    {
        return (A.b > B.b);
    }
};
priority_queue <name, vector <name>, compar> q;

int start[50002], t[3][250002], cost[250002], drum[50002];
bitset <50002> viz;

int main()
{
    int m, n, k = 0, x, y, c;
    f = fopen("dijkstra.in", "r");
    g = fopen("dijkstra.out", "w");
    fscanf(f, "%d %d", &n, &m);
    for (int i = 1;i <= m;i++)
    {
        fscanf(f, "%d %d %d", &x, &y, &c);
        t[0][++k] = y;
        t[1][k] = start[x];
        start[x] = k;
        cost[k] = c;
    }
    for (int i = 2;i <= n;++i)
        drum[i] = 2000000000;
    q.push({ 1,0 });
    int nod, vecin, dist, p;
    while (!q.empty())
    {
        name val;
        val = q.top();
        nod = val.a;
        q.pop();
        if (!viz[nod])
        {
            p = start[nod];
            while (p)
            {
                vecin = t[0][p];
                dist = cost[p] + drum[nod];
                if (dist < drum[vecin])
                {
                    drum[vecin] = dist;
                    q.push({ vecin,dist });
                }
                p = t[1][p];
            }
            viz[nod] = 1;
        }
    }
    for (int i = 2;i <= n;++i)
        if (drum[i] == 2000000000)
            fprintf(g, "0 ");
        else
            fprintf(g, "%d ", drum[i]);
    fclose(f);
    fclose(g);
    return 0;
}