#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>

using namespace std;

#pragma GCC diagnostic warning "-w"


#define MAXN 50001
#define lc(x) (x<<1)
#define rc(x) ((x<<1)+1)
#define pa(x) (x>>1)
#define MY_INF 0x7F7F7F7F7F7F7F7FULL
typedef unsigned long long ull;

vector<pair<long long, long long> > gr[MAXN];
ull distances[MAXN];

long long n, m, s, d, k;

// heap implementation
long long heap[MAXN], hsize;
long long hpoz[MAXN];



void hp_decrease_key(long long i)
{
    while (i > 1 && distances[heap[i]] < distances[heap[pa(i)]])
    {
        long long tmp = heap[i];
        long long tmp_pos = hpoz[heap[i]];
        hpoz[heap[i]] = hpoz[heap[pa(i)]];
        heap[i] = heap[pa(i)];
        hpoz[heap[pa(i)]] = tmp_pos;
        heap[pa(i)] = tmp; 

        i = pa(i);
    }
}

void hp_min_heapify(long long pos)
{
    long long mp = pos;
    if (lc(mp) <= hsize && distances[heap[lc(mp)]] < distances[heap[mp]])
        mp = lc(mp);
    if (rc(mp) <= hsize && distances[heap[rc(mp)]] < distances[heap[mp]])
        mp = rc(mp);

    if (mp != pos)
    {
        long long tmp = heap[pos];
        long long tpoz = hpoz[heap[pos]];
        hpoz[heap[pos]] = hpoz[heap[mp]];
        heap[pos] = heap[mp];

        hpoz[heap[mp]] = tpoz;
        heap[mp] = tmp;

        hp_min_heapify(mp);
    }

}

void hp_insert(long long val)
{
    heap[++hsize] = val;
    hpoz[val] = hsize;

    hp_decrease_key(hsize);
}

long long hp_pop()
{
    long long min = heap[1];
    hpoz[min] = 0;
    hsize--;
    
    if (hsize > 0)
    {
        heap[1] = heap[hsize+1];
        hpoz[heap[1]] = 1;
        hp_min_heapify(1);
    }
    return min;
}



void dijkstra(long long src)
{
    memset(distances, 0x7f, sizeof(ull) * (n + 1));
    hsize = 0;

    hp_insert(src);
    distances[src] = 0;

    while (hsize > 0)
    {
        long long crt = hp_pop();

        for (vector<pair<long long, long long> >::iterator it = gr[crt].begin();
                it != gr[crt].end() ; ++it)
        {
            if (distances[(*it).first] == MY_INF)
            {
                distances[(*it).first] = distances[crt] + (*it).second;
                hp_insert((*it).first);
            }
            else if (distances[(*it).first] > distances[crt] + (*it).second)
            {
                distances[(*it).first] = distances[crt] + (*it).second;
                hp_decrease_key(hpoz[(*it).first]);
            }
        }
    }
}

int main()
{
    long long T;

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%lld%lld", &n, &m);
    for (long long i = 0 ; i < m ; ++i)
    {
        long long x, y, time;
        scanf("%lld%lld%lld", &x, &y, &time);

        gr[x].push_back(make_pair(y, time));
    }

    dijkstra(1);

    for (int i = 1; i < n; ++i)
    {
        printf("%d ", distances[i+1]);
    }
    printf("\n");

    return 0;
}