#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 lHeap;
forward_list<pr> G[NMAX];
int d[NMAX], H[NMAX], P[NMAX];

inline void _swap(int& x, int& y) {int aux = x; x = y; y = aux;}
void DownHeap(int k)
{
    for(int son = k << 1; son <= lHeap; k = son, son <<= 1)
    {
        if(son < lHeap && d[H[son]] > d[H[son + 1]])
            ++son;
        if(d[H[k]] <= d[H[son]]) return;
        _swap(P[H[k]], P[H[son]]);
        _swap(H[k], H[son]);
    }
}
void UpHeap(int k)
{
    for(int key = d[H[k]], f = k >> 1; k > 1 && key < d[H[f]]; k = f, f >>= 1)
    {
        _swap(P[H[k]], P[H[f]]);
        _swap(H[k], H[f]);
    }
}

inline void push(int x)
{
    H[++lHeap] = x;
    P[x] = lHeap;
    UpHeap(lHeap);
}
inline int pop()
{
    int ans = H[1];
    H[1] = H[lHeap--];
    P[H[1]] = 1;
    DownHeap(1);
    return ans;
}

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(push(1); lHeap; )
    {
        x = pop();
        for(auto& y : G[x])
        {
            if(d[y.first] > d[x] + y.second)
            {
                d[y.first] = d[x] + y.second;
                if(!P[y.first]) push(y.first);
                else UpHeap(P[y.first]);
            }
        }
    }
    replace(d, d + N + 1, oo, 0);
    copy(d + 2, d + N + 1, ostream_iterator<int>(out, " "));

    return EXIT_SUCCESS;
}