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

using namespace std;

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

#define MAXN 50005

int N,M;
/// primul element e nodul
/// al doilea element e costul

vector< pair<int ,int> > G[MAXN]; /// array

int dist[MAXN];
/// primul element e cost
/// al doilea element e nodul
priority_queue< pair<int, int> > pq;

int main()
{
    pair<int, int> a, b;
    a = make_pair(0, 0);
    b = make_pair(10, 10);

    a.second;

    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    f>>N>>M;
    for(int i=1; i<=M; i++)
    {
        int node1, node2, cost;
        f>>node1>>node2>>cost;
        G[node1].push_back(make_pair(node2, cost));
    }

    pq.push(make_pair(0, 1));
    while (!pq.empty())
    {
        /// n IS AN INT. and it is the current node
        int n = pq.top().second;
        pq.pop();

        for (int i = 0; i < G[n].size(); ++i)
        {
            if (dist[G[n][i].first] > dist[n] + G[n][i].second)
            {
                dist[G[n][i].first] = dist[n] + G[n][i].second;
                pq.push(make_pair(-dist[G[n][i].second], G[n][i].first));
            }
        }
    }

    for (int i = 2; i <= N; i++)
    {
        if (dist[i] == 0x3f3f3f3f)
        {
            dist[i] = 0;
        }
        g << dist[i] << ' ';
    }
    g << endl;

    return(0);
}