#include <bits/stdc++.h>
#define nmax 50001
#define inf (1ULL<<31)
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int,int>> a[nmax];
vector<pair<int,int>>::iterator it;
set<pair<int,int>> s;
unsigned d[nmax],n,m,i,x,y,cost,p=1,dist,nod,dest;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        a[x].push_back(make_pair(y,cost));
    }
    for(i=1;i<=n;i++) d[i]=inf;
    d[p]=0;
    s.insert(make_pair(0,p));
    while(!s.empty())
    {
        nod=s.begin()->second;
        dist=s.begin()->first;
        s.erase(s.begin());
        for(it=a[nod].begin();it!=a[nod].end();it++)
        {
            dest=it->first;
            cost=it->second;
            if(d[dest]>d[nod]+cost)
            {
                if(d[dest]!=inf) s.erase(s.find(make_pair(d[dest],dest)));
                d[dest]=d[nod]+cost;
                s.insert(make_pair(d[dest],dest));
            }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]!=inf) fout<<d[i]<<" ";
        else fout<<"0 ";
    return 0;
}