#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cassert>
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 0x7F7F7F7F

vector<pair<int, int> > gr[MAXN];
int distances[MAXN];
int n, m;

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



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

        i = pa(i);
    }
}

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

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

        hp_min_heapify(mp);
    }

}

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

    hp_decrease_key(hsize);
}

int hp_pop()
{
    int 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(int src)
{
    memset(distances, 0x7f, sizeof(int) * (n + 1));
    hsize = 0;

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

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

        for (auto 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()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

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

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

    dijkstra(1);

    for (int i = 2; i <= n; ++i)
    {
        if (MY_INF == distances[i])
        {
            printf("0 ");
        }
        else
        {
            printf("%d ", distances[i]);

        }
    }
    printf("\n");

    return 0;
}