#include <bits/stdc++.h>
#define nmax  50001
#define inf 1000000001
#define ss second
#define ff first
using namespace std;
priority_queue<pair<int, int > > q;
vector <pair<int, int> >v[nmax];
int N,M;
int d[nmax];
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>N>>M;
    for(int i=1;i<=M;++i)
    {
        int x,y,z;
        fin>>x>>y>>z;
        v[x].push_back({y,z});
    }
    for(int i=2;i<=N;++i)d[i]=inf;
    d[1]=0;
    q.push({0,1});
    while(!q.empty())
    {
        int cost=-q.top().ff;
        int nod=q.top().ss;
        q.pop();
        if(cost!=d[nod])
            continue;
        for(auto x: v[nod])
            if(d[x.ff]>d[nod]+x.ss)
        {
            d[x.ff]=d[nod]+x.ss;
            q.push({-d[x.ff],x.ff});
        }
    }
    for(int i=2;i<=N;++i)fout<<d[i]<<" ";
    return 0;
}