#include <bits/stdc++.h>

using namespace std;

const int NMAX = 50000;

struct edge
{
    int y,cost;
    edge() = default;
    edge(int _y, int _cost) : y(_y), cost(_cost) {}
};

int heap[NMAX + 1], heap_size;
int pos_heap[NMAX + 1];
int dist[NMAX + 1];

bool found[NMAX + 1];

vector<edge> graph[NMAX + 1];

void heapSwap(int pa, int pb)
{
    swap(pos_heap[heap[pa]], pos_heap[heap[pb]]);
    swap(heap[pa], heap[pb]);
}

void heapUp(int pos)
{
    int father = (pos >> 1);
    while(pos > 1 && dist[heap[pos]] < dist[heap[father]])
    {
        heapSwap(pos,father);

        pos = father;
        father = (pos >> 1);
    }
}

void heapDown(int pos)
{
    int left_son = (pos<<1), right_son = (pos<<1)+1, best;
    while(left_son <= heap_size)
    {
        best = left_son;
        if(right_son <= heap_size && dist[heap[right_son]] < dist[heap[left_son]]) best = right_son;

        if(dist[heap[pos]] < dist[heap[best]]) break;

        heapSwap(pos,best);
        pos = best;
        left_son = (pos<<1);
        right_son = left_son+1;
    }
}

void heapInsert(int node)
{
    heap[++heap_size] = node;
    pos_heap[node] = heap_size;

    heapUp(heap_size);
}

void heapErase(int node)
{
    int pos = pos_heap[node];
    heapSwap(pos, heap_size);
    --heap_size;

    heapDown(pos);
}

void heapUpdate(int node)
{
    heapUp(pos_heap[node]);
}

void dijkstra(int first)
{
    heapInsert(first);
    dist[first] = 0;
    found[first] = 1;

    while(heap_size > 0)
    {
        int node = heap[1];
        heapErase(node);

        for(auto i:graph[node])
        {
            int y=i.y, cost=i.cost;

            if(!found[y])
            {
                found[y] = true;
                dist[y] = dist[node] + cost;
                heapInsert(y);
            }
            else if(dist[y] > dist[node] + cost)
            {
                dist[y] = dist[node] + cost;
                heapUpdate(y);
            }
        }
    }
}

int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");

    int n,m,x,y,cost;

    fin>>n>>m;
    for(int i=0; i<m; ++i)
    {
        fin>>x>>y>>cost;
        graph[x].emplace_back(y,cost);
    }

    dijkstra(1);

    for(int i=2; i<=n; ++i) fout<<dist[i]<<' ';

    return 0;
}