#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#include <bitset>
#include <list>
#include <algorithm>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
class nod
{
public:
    nod(short x, short cost) { nod::x = x; nod::cost = cost; }
    short x, cost;
};
unsigned int n, m;
const unsigned int x0 = 1, INF = 0xFFFFFFFF;
unsigned int dmin[50005];
vector<list<nod> > c(50005);

void dijkstra()
{
    int i;
    for (i = 2; i <= n; ++i)
        dmin[i] = INF;
    dmin[x0] = 0;

    queue<int> q;
    q.push(x0);
    bitset<50005> viz;

    while (!q.empty())
    {
        viz[q.front()] = 1;
        for (list<nod>::iterator it = c[q.front()].begin();
                it != c[q.front()].end(); ++it)
            {
                if ( !viz[it->x] )
                    q.push(it->x);
                dmin[it->x] = min(dmin[it->x], dmin[q.front()] + it->cost);
            }
        q.pop();
    }
}
int main()
{
    int i, j, x, y;
    f >> n >> m;
    for (i = 1; i <= m; ++i)
    {
        f >> x >> y >> j;
        c[x].push_front(nod(y, j));
    }

    dijkstra();
    for (int i = 2 ; i <= n ; ++i)
        if (dmin[i] == INF)
            g << 0 << " ";
        else
            g << dmin[i] << " ";
    f.close();
    g.close();
    return 0;
}