#include <bits/stdc++.h>
#define ff first
#define ss second
#define NMAX 50001
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const string file = "";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647;
vector <pi> v[NMAX];
priority_queue <pi> Q;
int d[NMAX];
int chec[NMAX];
int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    int m,n,i,j,x,y,z;
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>z;
        v[x].push_back({y,z});
    }
    for(i=2;i<=NMAX;++i)
    d[i]=inf;
    Q.push({0,1});
    while(Q.size())
    {
        int nod=Q.top().second;
        Q.pop();
        chec[nod]=0;
        for(auto x: v[nod])
        {
            if(d[nod]+x.second<d[x.first])
            {
                d[x.first]=d[nod]+x.second;
                if(chec[x.first]==0) Q.push({-d[x.first],x.first}),chec[x.first]=1;
            }
        }
    }
    for(i=2;i<=n;++i)
    if(d[i]!=inf)fout<<d[i]<<" ";
    else fout<<0<<" ";
    return 0;
}