#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()
{
    unsigned int i, j;
    for (i = 2; i <= n; ++i)
        dmin[i] = INF;

    bitset<50005> viz;

    int minim, pmin = 0;
    for ( i = 1; i <= n; ++i )
    {
        minim = INF;
        for ( j = 1; j <= n; ++j )
            if ( dmin[j] < minim && !viz[j] )
                minim = dmin[j], pmin = j;

        viz[pmin] = 1;
        for (list<nod>::iterator it = c[pmin].begin();
                it != c[pmin].end(); ++it)
            dmin[it->x] = min(dmin[it->x], dmin[pmin] + it->cost);
    }
}
int main()
{
    unsigned 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 (i = 2 ; i <= n ; ++i)
        if (dmin[i] == INF)
            g << 0 << " ";
        else
            g << dmin[i] << " ";
    f.close();
    g.close();
    return 0;
}