#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define mmax 250005
#define inf 20000000000
using namespace std;
fstream f1("dijkstra.in", ios::in);
fstream f2("dijkstra.out", ios::out);
int n, m, viz[nmax];
long long dist[nmax];
vector<pair<int, int> > v[nmax];
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>>  > q;
void citire()
{
    int i, x, y,c;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        v[x].push_back({y,c});
    }
}
void solutie()
{
    int i, nod, vec, cost, ct;
    for(i=2; i<=n; i++)
        dist[i]=inf; ///pui infinit la toate cu exceptia lui 1

    q.push({0,1});
    while(!q.empty())
    {
       nod=q.top().second; ct=q.top().first; q.pop(); viz[nod]=1;//ai marcat nodul, niciodata de acum incolo nu ii vei mai actualiza distanta

       if(dist[nod]==ct) //daca nodul a fost proaspat actualizat si retine informatia corecta (altfel sigur exista un alt nod=nod cu distanta dist[nod] in coada si nu are sens sa faci actualizarea decat pe ala )
       for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
           if(!viz[(*it).first]) //daca exista vecini neactualizati ai nodului, posibili candidati cu dist minima
       {
           vec=(*it).first;
           cost=(*it).second;

           if(dist[vec]> dist[nod]+cost) ///daca se poate ajunge la ei pe un drum mai scurt prin nod
           {
                dist[vec]= dist[nod]+cost; //actualizeaza dist-ul
                q.push({dist[vec], vec}); //pune in coada cu priorit. nodul cu distanta actualizata
           }
       }
    }
}
void afis()
{
    int i;
    for(i=2; i<=n; i++)
        if(dist[i]!=inf) f2<<dist[i]<<' ';
        else f2<<0<<' ';
}
int main()
{
    citire();
    solutie();
    afis();
    return 0;
}