#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

#define NMAX 100005
#define INF 100000000

using namespace std;

int dist[NMAX];
int vizitat[NMAX];
vector<int> cost[NMAX];
vector<int> graph[NMAX];
priority_queue< pair<int, int> > heap;

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int N, M;
    f>>N>>M;
    int x, y, c;
    for(int i = 1; i <= M; i++)
    {
        f>>x>>y>>c;
        graph[x].push_back(y);
        cost[x].push_back(c);
        dist[i] = INF;
        heap.push(make_pair((-1)*INF, i));
    }
    dist[1] = 0;
    heap.push(make_pair((-1)*dist[1], 1));
    while(!heap.empty())
    {
        int index = -1;
        pair<int, int> p = heap.top();
        index = p.second;
        if(dist[index] == p.first*(-1))
        {
            vizitat[index] = 1;
            int lim = graph[index].size();
            for(int t = 0; t < lim; t++)
            {
                int vecin = graph[index][t];
                if(dist[vecin] > dist[index] + cost[index][t])
                {
                    dist[vecin] = dist[index] + cost[index][t];
                    heap.push(make_pair((-1)*dist[vecin], vecin));
                }
            }
        }
        heap.pop();
    }

    for(int i = 2; i <= N; i++)
    {
        if(dist[i] == INF) dist[i] = 0;
        g<<dist[i]<<" ";
    }
    return 0;
}