#include <bits/stdc++.h>
#define INF numeric_limits<int>::max()

using namespace std;

ifstream f("djikstra.in");
ofstream g("djikstra.out");
int n;
vector< vector< pair< int,int> > > a;
vector<int> d;
priority_queue< pair<int,int> > q;

/*void citire()
{
    int m,x,y,c;
    f>>n>>m;
    a=vector< vector< pair<int,int> > >(n+1);
    d=vector<int>(n+1,INF);
    while(m)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(y,c));
        m--;
    }
}*/

void djikstra(int x)
{

    q.push({0,x});
    d[x]=0; //costul de la x la x e 0
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        for(vector< pair<int,int> >::iterator i=a[x].begin();i!=a[x].end();i++) //parcurg adiacentele lui x
        {
            if(d[x]+i->second < d[i->first]) // compar cu costul dinainte
            {
                d[i->first]=d[x]+i->second;  //inlocuiesc
                q.push({-d[i->first],i->first});//adaug in multime si retin anteriorul
            }
        }
    }
}

void afisare()
{
    int i;
    for(i=2;i<=n;i++) if(d[i]==INF) g<<"0 "; else g<<d[i]<<" ";
}

int main()
{
        int m,x,y,c;
    f>>n>>m;
    a=vector< vector< pair<int,int> > >(50001);
    d=vector<int>(50001,INF);
    while(m)
    {
        f>>x>>y>>c;
        a[x].push_back({y,c});
        m--;
    }
    djikstra(1);
    afisare();
    return 0;
}