#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;
    used[1]=1;
    while(!q.empty())
    {
        pair<int,int> per=q.top();
        int nod=per.second;
        int dist=per.first;
        q.pop();
        for(auto it:g[nod])
        {
            int newnod=it.first;
            int newdist=it.second+dist;
            d[newnod]=min(d[newnod],newdist);
            if(!used[newnod])
            {
                used[newnod]=1;
                q.push({newdist,newnod});
            }
        }
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<' ';
    return 0;
}