// Dijkstra.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

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

using namespace std;

const int MAX_N = 50000 + 1;
const int MAX_M = 250000 + 1;
const int oo = static_cast<int>(1e9);

ifstream fin{ "dijkstra.in" };
ofstream fout{ "dijkstra.out" };


vector<vector<tuple<int, int>>> adj(MAX_N, vector<tuple<int, int>>());
int N, M;
int s;


vector<int> d(MAX_N);


void INITIALIZE_SINGLE_SOURCE()
{
    for (int i = 1; i <= N; ++i)
    {
        d[i] = oo;
    }

    d[s] = 0;
}


void RELAX(int u, int v, int weight)
{
    if (d[u] + weight < d[v])
    {
        d[v] = d[u] + weight;
    }
}


void Dijkstra()
{
    INITIALIZE_SINGLE_SOURCE();


    function<bool(const int&, const int&)> compare = [](const int& x, const int& y) {
        return d[x] > d[y];
    };

    priority_queue<int, vector<int>, decltype(compare)> Q(compare);


    for (int u = 1; u <= N; ++u)
    {
        Q.push(u);
    }


    while (Q.empty() == false)
    {
        int u = Q.top();
       
        for (auto& edge : adj[u])
        {
            int v = get<0>(edge);
            int weight = get<1>(edge);

            RELAX(u, v, weight);
        }

        Q.pop();
    }
}


int main()
{
    fin >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int u, v, weight;
        
        fin >> u >> v >> weight;

        adj[u].push_back({ v, weight });
    }

    s = 1;

    Dijkstra();

    for (int u = 2; u <= N; ++u)
    {
        if (d[u] == oo)
        {
            fout << 0 << " ";
        }
        else
        {
            fout << d[u] << " ";
        }
    }

    fout << endl;
}