#include <iostream>
#include <queue>
#define pii pair<int, int>
#include <vector>
#include <climits>
#include <fstream>
#define INF INT_MAX

using namespace std;

priority_queue < pii,          /// tipul elementelor din coada
                 vector<pii>, /// peste ce container o sa fie adaptor
                greater<pii>  /// comparator, pt ca default e max
                > pq;           /// variabila coada efectiv
/*
operatii :
    pq.empty() -> bool/e sau nu vida coada
    pq.pop() -> elimina primul element
    pq.top() -> returneaza primul element -> va fi de tip pii
    pq.push(obiect) -> insereaza obiect in coada
                    -> obiect e de tipul pii

    default perechile se ordoneaza dupa primul camp
    (nod,cost) -> ordoneaza dupa nod
    !!! -> in coada (si implicit in graf) memoram perechile in forma
    (cost,nod)
*/

vector <pii> G[50001];
vector <int> d;
int n,m;
void read()
{
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    int x,y,c;
    while(fin>>x>>y>>c)
        G[x].push_back({c,y});
}

void dijks()
{
    d.assign(n+1,INF);
    pq.push({0,1});
    d[1]=0;
    while(!pq.empty())
    {
        pii curent = pq.top();
        pq.pop();

        for( auto nod : G[curent.second])
        {
            if(d[nod.second] > d[curent.second] + nod.first)
            {
                d[nod.second] = d[curent.second] + nod.first;
                pq.push({d[nod.second],nod.second});
            }
        }
    }
}

void print()
{
    ofstream fout("dijkstra.out");
    for(int i=2;i<=n;i++)
        if(d[i]==INF)
            fout<<"0 ";
        else
            fout<<d[i]<<" ";

}

int main()
{
   read();
   dijks();
   print();
   return 0;
}