#include <iostream>
#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int maxn = 5e4+5, inf = 0x3f3f3f3f;

typedef struct nod
{
    int i, c;
    nod *next;
} *pnod;

pnod a[maxn];
int n, m, i, x, y, z, d[maxn];

void add(int where, int what, int cost)
{
    pnod q = new nod;
    q -> next = a[where];
    q -> i = what;
    q -> c = cost;
    a[where] = q;
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        f >> x >> y >> z;
        add(x, y, z);
    }

    for(i = 2; i <= n; i ++)
        d[i] = inf;
    for(i = 1; i <= n; i ++)
    {
        for(pnod j = a[i]; j != NULL; j = j -> next)
        {
            d[j -> i] = min(d[j -> i], d[i] + j -> c);
        }
    }
    for(i = 2; i <= n; i ++)
        g << d[i] << ' ';
    return 0;
}