#include <bits/stdc++.h>
#define pii pair < ll , ll >
#define pb push_back
#define ll int

namespace FastRead
{
    char __buff[5000];ll __lg = 0 , __p = 0;
    char nc()
    {
        if(__lg == __p){__lg = fread(__buff , 1 , 5000 , stdin);__p = 0;if(!__lg) return EOF;}
        return __buff[__p++];
    }
    template<class T>void read(T&__x)
    {
        T __sgn = 1; char __c;while(!isdigit(__c = nc()))if(__c == '-')__sgn = -1;
        __x = __c - '0';while(isdigit(__c = nc()))__x = __x * 10 + __c - '0';__x *= __sgn;
    }
}

using namespace FastRead;
using namespace std;

const ll N = 5e4 + 10;

ll n , m;
ll d[N];
vector < pii > G[N];

struct Heap
{
    ll sz;
    ll *heap , *pos;

    Heap(ll n)
    {
        pos = new ll[n + 10];
        heap = new ll[n + 10];
        sz = 0;

        for(int i = 1 ; i <= n ; i++)
            pos[i] = 0;
    }

    void upg(ll node)
    {
        while(node > 1)
        {
            if(d[heap[node]] < d[heap[node / 2]])
            {
                swap(heap[node] , heap[node / 2]);
                swap(pos[heap[node]] , pos[heap[node / 2]]);
                node /= 2;
            }
            else break;
        }
    }

    void dem(ll node)
    {
        while(1)
        {
            ll son = 2 * node;

            if(son + 1 <= sz && d[heap[son]] > d[heap[son + 1]])
                son++;

            if(son <= sz && d[heap[node]] > d[heap[son]])
            {
                swap(heap[node] , heap[son]);
                swap(pos[heap[node]] , pos[heap[son]]);
                node = son;
            }
            else break;
        }
    }

    void add(ll x)
    {
        heap[++sz] = x;
        pos[x] = sz;
        upg(sz);
    }

    void rem()
    {
        pos[heap[1]] = 0;
        heap[1] = heap[sz];
        pos[heap[1]] = 1;
        --sz;
        dem(1);
    }
} H(N);


void dijkstra()
{
    for(ll i = 1 ; i <= n ; i++)
        d[i] = INT_MAX;

    d[1] = 0;
    H.add(1);

    while(H.sz)
    {
        ll node = H.heap[1];
        H.rem();

        for(auto i : G[node])
            if(d[i.first] > d[node] + i.second)
            {
                ll p = H.pos[i.first];
                d[i.first] = d[node] + i.second;

                if(p) H.upg(p);
                else H.add(i.first);
            }
    }
}

signed main()
{
    freopen("dijkstra.in" , "r" , stdin) , freopen("dijkstra.out" , "w" , stdout);
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);

    read(n) , read(m);

    for(ll i = 1 ; i <= m ; i++)
    {
        ll x , y , c;
        read(x) , read(y) , read(c);
        G[x].pb({y , c});
    }

    dijkstra();

    for(ll i = 2 ; i <= n ; i++)
        cout << (d[i] == INT_MAX ? 0 : d[i]) << ' ';

    return 0;
}