#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
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)
    {
        if (distanta[i] != Inf)
            fout << distanta[i] << ' ';
        else fout << 0 << ' ';
    }
}
void Dijkstra(int nod_start)
{
    priority_queue<P, VP, greater<P> > Q;   //min-HEAP (coada de prioritati pairuri. 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();

        if (cost_curent > distanta[nod_curent])    //daca am gasit intre timp alt cost minim pentru nod_curent, nu mai pornim algoritmul si pentru costul vechi (scoatem costul vechi minim din coada)
            continue;

        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 muchiile intr-un singur sens, graful fiind orientat
    }
}