#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int MaxN = 50005;
const int Inf = 0x3f3f3f3f;

using P = pair <int, int>;
using VP = vector <P>;
using VVP = vector <VP>;
VVP G;  //graful propriu-zis
int n, m;
int distanta[MaxN]; // aici retinem distanta de la nodul de start, la nodul i (d[i] = distanta de la nodul 1 la nodul i)

void Citire();
void Dijkstra(int nod_start);

int main()
{
    Citire();
    for (int i = 1; i <= n; ++i)
        distanta[i] = Inf;
    distanta[1] = 0;

    Dijkstra(1);

    for (int i = 2; i <= n; ++i)
        fout << distanta[i] << ' ';
}
void Dijkstra(int nod_start)
{
    priority_queue<P, VP, greater<P> > Q;   //min-HEAP (coada de prioritati pair-uri. Elementele sunt ordonate in functie de cele mai mici costuri) (in functie de .first)
    Q.push({distanta[nod_start], nod_start});     // adaugam nodul de start in coada, el avand costul 0;

    while (!Q.empty())
    {
        int cost_curent = Q.top().first;       //extragem costul nodului din capul cozii
        int nod_curent = Q.top().second;       //si pe acesta

        Q.pop();

        for (int i = 0; i < G[nod_curent].size(); ++i)
        {
           int nod_vecin = G[nod_curent][i].first; //extragem nodul vecin
           int cost_vecin = G[nod_curent][i].second; //extragem costul drumului catre vecin

           if (distanta[nod_curent] + cost_vecin < distanta[nod_vecin])
           {
               distanta[nod_vecin] = distanta[nod_curent] + cost_vecin;     //actualizam distanta minima pana la nodul vecin

               Q.push(make_pair(distanta[nod_vecin], nod_vecin)); //introducem vecinul si distanta minima pana la el in coada
           }
        }
    }
}

void Citire()
{
    fin >> n >> m;
    int x, y, z;

    G = VVP(n + 1);

    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y >> z;
        G[x].push_back(make_pair(y, z));  // retinem graful intr-un singur sens, acesta fiind orientat
    }
}