#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > q;
int n,m,i,j,u,v,x,d[50005];
const int INF=1<<30;
bool used[50005];
vector<pair<int,int> > g[50005];
int main()
{
    q.push({0,1});
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>u>>v>>x;
        g[u].push_back({v,x});
    }
    for(i=2;i<=n;i++)
        d[i]=INF;
    while(!q.empty())
    {
        pair<int,int> per=q.top();
        int nod=per.second;
        int dist=per.first;
        q.pop();
        if(used[nod])continue;
        used[nod]=1;
        for(auto it:g[nod])
        {
            int newnod=it.first;
            int newdist=it.second+dist;
            if(newdist<d[newnod]&&!used[newnod])
            {
                d[newnod]=newdist;
                q.push({newdist,newnod});
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==INF)
            fout<<0<<' ';
        else fout<<d[i]<<' ';
    }
    return 0;
}