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

using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

#define INF 2147483647

void citire (vector<vector < pair <int, int> > > &G, int N, int M)
{
    int x, y, cost;
    int i;
    for (i = 1; i <= M; i++)
    {
        fin >> x >> y >> cost;
        G[x].push_back (make_pair (y, cost));
    }
}

void Dijkstra (int nod_Start, vector< vector < pair <int, int> > > G, priority_queue <int, vector <int> > &myheap, vector<int> &D, vector<int> &viz, int N)
{
    int i;
    D[nod_Start] = 0;
    myheap.push (nod_Start);
    while (!myheap.empty())
    {
        int nod = myheap.top(); //Scoatem primul nod din heap
        myheap.pop();
        if(viz[nod])
            continue;
        for (i = 0; i < (int)G[nod].size(); i++)
        {
            int Vecin = G[nod][i].first;
            int Cost = G[nod][i].second;
            if (D[nod] + Cost < D[Vecin])
            {
                D[Vecin] = D[nod] + Cost;
                if (viz[Vecin] == 0)
                {
                    myheap.push (Vecin);
                }
            }
        }
        viz[nod] = 1;
    }
}

void Afiseaza (int N, vector<int> D)
{
    for (int i = 2; i <= N; i++)
    {
        if (D[i] != INF)
            fout << D[i] << " ";
        else
            fout << "0 ";
    }
}

int main()
{
    priority_queue <int, vector <int> > myheap;//folosim un min heap, max heap e doar priority_queue <int>
    int N, M;
    fin >> N;
    fin >> M;
    vector<vector < pair <int, int> > > G (N + 1);
    vector<int> D (N + 1, INF);
    vector<int> viz (N + 1, 0);
    citire (G, N, M);
    Dijkstra (1, G, myheap, D, viz, N);
    Afiseaza (N, D);
}