#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define DIM 5005
#define INF DIM*1000

using namespace std;

vector<pair<int, int>> listaAdiacenta[DIM]; /// aici se creeaza un vector de vectori de perechi (fiecare element
                                            ///al vectorului are 2 campuri de tip int),
                                            /// in care o sa pastram lista de adiacenta al fiecarui nod.
set<pair<int, int>> q; ///creem un set in care pastram nodul si distanta acestuia;
                            /// perechile din set sunt ( dist[nod], nod)

int    dist[DIM], x, y, c, nr_varfuri, nr_muchii, k;

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

int main()
{
    fin >> nr_varfuri >> nr_muchii;
    for (int i = 1; i <= nr_muchii; i++)
    {
        fin >> x >> y >> c; /// citim legaturile care se formeaza intre noduri si costul acestora
        ///Pentru graf orientat:
        //listaAdiacenta[x].push_back(make_pair(y, c)); /// in lista de adiacenta a nodului de plecare adaugam
                                                        /// o pereche formata din nodul si costul adiacent

        ///Daca graful este neorientat adaugam:
        listaAdiacenta[x].push_back( make_pair(y, c) );
    }

    for (int i = 1; i <= nr_varfuri; i++)
    {
        dist[i] = INF; ///initializam distantele fiecarui nod ca fiind infinit
    }

    ///Consideram ca 1 este nodul de plecare.
    dist[1] = 0; /// distanta nodului de plecare este 0

    q.insert(make_pair(0, 1)); /// adaugam in set distanta nodului 1;
    ///in set tinem perechi(cost, nod) doar pentru nodurile nealese inca si actualizate macar o data;
    ///in paralel tinem distantele minime la noduri si in vectorul    dist


    while (!q.empty()) ///cat timp exista elemente in set
    {
        int vertex = q.begin()->second; ///din primul element al setului, pastram al doilea
                                                ///camp din pereche (nodul), pentru ca apoi sa
        q.erase(q.begin());             ///il stergem

        for (int i = 0; i < listaAdiacenta[vertex].size(); i++) ///parcurgem lista de adiacenta a nodului curent
        {
            int neighbour = listaAdiacenta[vertex][i].first; ///nod vecin
            int cost = listaAdiacenta[vertex][i].second;   ///costul pana la nodul vecin

            if (dist[neighbour] > dist[vertex] + cost)  ///daca distanta nodului vecin e mai mare
            {                            ///decat distanta nodului curent + costul pana la acesta, trebuie sa
                                        ///actualizam valoarea din vectorul    dist al vecinului.

                q.erase(make_pair(dist[neighbour], neighbour)); ///cauta in set daca exista acest nod si il sterge
                dist[neighbour] = dist[vertex] + cost;      ///actualizeaza noua distanta a nodului vecin
                q.insert(make_pair(dist[neighbour], neighbour));   /// adaugam parechea cu costul actualizat si nod

                ///Acest if actualizeaza distantele astfel incat sa aiba cele mai mici valori posibile( cel mai scurt drum
                                                                                            ///pana la nodul respectiv).
            }
        }
    }

    ///Trebuie sa afisam distanta de la nodul de pornire pana la toate nodurile grafului.
    for (int i = 2; i <= nr_varfuri; i++) ///parcurgem toate nodurile grafului, in afara de cel de pornire (in cazul nostru
    {                                                                                                   /// nodul 1
        if (dist[i] == INF) /// daca nu s-a actualizat niciodata distanta acelui nod ( nu se poate ajunge la acest nod
            fout << "0 ";         ///din nodul de pornire ) , afiseaza distanta 0.
        else
            fout << dist[i] << " ";
    }
}