#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
#define g g

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

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

int dist[MAXN];
int viz[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 node = pq.top().second;
        pq.pop();

        if (viz[node] == 1)
        {
            continue;
        }
        viz[node] = 1;
#if 0
        for (int i = 1; i <= N; ++i)
        {
            std::cout << i << ": ";
            for (int j = 0; j < G[i].size(); ++j)
            {
                std::cout << " (" << G[i][j].first << ' ' << G[i][j].second << ") ";
            }
            std::cout << std::endl;
        }
        std::cout << std::endl;

        std::cout << node << std::endl;
        for (int i = 1; i <= N; i++)
        {
            std::cout << dist[i] << ' ';
        }
        std::cout << std::endl;
        std::cout << std::endl;
#endif
        for (int i = 0; i < G[node].size(); ++i)
        {
            if (dist[G[node][i].first] > dist[node] + G[node][i].second)
            {
                dist[G[node][i].first] = dist[node] + G[node][i].second;
                pq.push(make_pair(-dist[G[node][i].first], G[node][i].first));
            }
        }
    }

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

    return(0);
}