#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define inf 200000

vector <vector< pair <int, int> > > graph;
priority_queue < pair <int, int> > heap;
vector <int> Dist;
vector <bool> viz;

int n, m;

void dijkstra(int source)
{
    int i, x, y, cost;
    Dist[source] = 0;
    heap.push(make_pair(0, source));
    while(!heap.empty())
    {
        x = heap.top().second;
        heap.pop();
        viz[x] = true;
        for(i = 0; i < graph[x].size(); i++)
        {
            y = graph[x][i].first;
            cost = graph[x][i].second;
            if(Dist[y] > Dist[x] + cost)
            {
                Dist[y] = Dist[x] + cost;
                heap.push (make_pair(Dist[y], y));
            }
        }
        while(!heap.empty() && viz[heap.top().second])
            heap.pop();
    }
}


int main()
{
    int i, x, y, c;
    f >> n >> m;
    graph.resize(n);
    for(i = 0; i < m; i++)
    {
        f >> x >> y >> c;
        x--;
        y--;
        graph[x].push_back (make_pair(y, c));
    }
    Dist.resize(n, inf);
    viz.resize(n, false);
    dijkstra(0);
    for (i = 1; i < n; i++)
            g << Dist[i] << " ";
    return 0;
}