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

    bitset<50005> viz;
    queue<unsigned int> q;
    q.push(x0);
    while(!q.empty())
    {
        for (list<nod>::iterator it = c[q.front()].begin() ;
                it != c[q.front()].end() ;
                ++it)
            if ( dmin[q.front()] + it->cost < dmin[it->x] )
            {
                q.push(it->x);
                dmin[it->x] = dmin[q.front()] + it->cost;
            }
        q.pop();
    }
}
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));
    }

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