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

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);

    cin >> n >> m;

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

    dijkstra();

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

    return 0;
}