#include <queue>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <forward_list>

using namespace std;

const int NMAX = 50011;
const int oo = 1 << 29;
typedef pair<int, int> pr;

int d[NMAX];
bool was[NMAX];
forward_list<pr> G[NMAX];
priority_queue<pr, deque<pr>, greater<pr>> pQ;


int main()
{
    int N, M, x, y, c;
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    for(in >> N >> M; M; --M)
    {
        in >> x >> y >> c;
        G[x].push_front(pr(y, c));
    }
    fill(d, d + N + 1, oo);
    d[1] = 0;
    for(pQ.push(pr(0, 1)); !pQ.empty(); )
    {
        x = pQ.top().second; pQ.pop();
        if(true == was[x]) continue;
        was[x] = true;
        for(auto& y : G[x])
        {
            if(d[y.first] > d[x] + y.second)
            {
                d[y.first] = d[x] + y.second;
                pQ.push(pr(d[y.first], y.first));
            }
        }
    }
    copy_if(d + 2, d + N + 1, ostream_iterator<int>(out, " "), [] (int& x) {if(oo == x) x = 0; return true;});
    out << '\n';
    return EXIT_SUCCESS;
}