#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
 
#define INF             (2147483647 - 20000)
#define MAX_NODES       50001
 
using namespace std;
 
int sol[MAX_NODES];
int heap[MAX_NODES], pos[MAX_NODES], h_i = 1;
vector<pair<int, int> > graf[MAX_NODES];
int n, m, x, y, w;

void heap_swap(int x, int y)
{
    pos[heap[x]] ^= pos[heap[y]];
    pos[heap[y]] = pos[heap[x]] ^ pos[heap[y]];
    pos[heap[x]] = pos[heap[x]] ^ pos[heap[y]];

    heap[x] ^= heap[y];
    heap[y] = heap[x] ^ heap[y];
    heap[x] = heap[x] ^ heap[y];
}

void upheap(int index)
{
    while (index > 1 && sol[heap[index]] < sol[heap[index >> 1]]) {
        heap_swap(index, index >> 1);
        index >>= 1;
    }
}


void downheap(int index)
{
    int i, j, min;

    while (index < h_i) {
        i = index << 1;
        j = i + 1;
        
        if (i >= h_i)
            break;

        if (j >= h_i)
            min = i;
        else
            min = sol[heap[i]] < sol[heap[j]] ? i : j;

        if (sol[heap[index]] > sol[heap[min]])
            heap_swap(index, min);
        else
            break;

        index = min;
    }
}

void heap_add(int x)
{
    heap[h_i] = x;
    pos[x] = h_i;

    if (sol[heap[h_i]] < sol[heap[h_i >> 1]])
        upheap(h_i);

    h_i++;
}

int heap_top()
{
    int min = heap[1];
    heap_swap(1, --h_i);
    downheap(1);
    return min;
}

void dijkstra()
{
    int node;
    heap_add(1);
    for (int i = 2; i <= n; i++)
        sol[i] = INF;
 
    while (h_i > 1) {
        node = heap_top();

        for (auto &it : graf[node]) {
            if (sol[node] + it.second < sol[it.first]) {
                sol[it.first] = sol[node] + it.second;

                if (!pos[it.first])
                    heap_add(it.first);
                else
                    upheap(pos[it.first]);
            }
        }
    }
}
 
int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
 
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> w;
        graf[x].push_back(make_pair(y, w));
    }
 
    dijkstra();

    for (int i = 2; i <= n; i++) {
        if (sol[i] == INF)
            out << 0 << ' ';
        else
            out << sol[i] << ' ';
    }
 
    return 0;
}