#include <bits/stdc++.h>
#define Dmax 50005
#define inf 1000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int N,M,P,D[Dmax],a,b,c,x,y;
vector < pair <int, int > >G[Dmax];
priority_queue < pair <int, int > , vector <pair <int, int> >, greater <pair <int, int> > >Q;

void citire()
{
    f>>N>>M;
    while(f>>a>>b>>c)
        G[a].push_back(make_pair(b,c));
    for(int i=1;i<=N;i++)
        D[i]=inf;
}
void Dijkstra(int nod)
{
    D[nod]=0;
    Q.push({0,nod});
    while(!Q.empty())
    {
        x=Q.top().first;
        y=Q.top().second;
        Q.pop();
        if(x > D[y])
            continue;
        for(unsigned int i=0;i<G[y].size();i++)
        {
            int Vecin = G[y][i].first;
            int Cost = G[y][i].second;
            if(D[Vecin] > D[y] + Cost)
            {
                D[Vecin] = D[y]+Cost;
                Q.push({D[Vecin],Vecin});
            }
        }
    }



}
void afisare()
{
    for(int i=2;i<=N;i++)
        if(D[i]==inf)
        g<<0<<" ";
        else
            g<<D[i]<<" ";
}

int main()
{
    citire();
    Dijkstra(1);
    afisare();
f.close();
g.close();
    return 0;
}