#include <iostream>
#include<cstdio>
#include<utility>
#include<vector>
#include<deque>
using namespace std;
deque<int> Q;
vector<pair<int,int> > v[50010];
int d[50010],q[50010],n,m,x,y,z,i;
int main()
{
    freopen("djikstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    cin>>n>>m;
    for(;m;m--)
    {
        cin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    for(i=2;i<=n;i++)d[i]=1000000000;
    Q.push_back(1);
    q[1]=1;
    vector<pair<int,int> >::iterator it;
    for(;Q.size();)
    {
        x=Q.front();
        Q.pop_front();
        q[x]=0;
        for(it=v[x].begin();it!=v[x].end();it++)
            if(d[it->first]>d[x]+it->second)
            {
                d[it->first]=d[x]+it->second;
                if(!q[it->first])
                {
                    q[it->first]=1;
                    Q.push_back(it->first);
                }
            }
    }
    for(i=2;i<=n;i++)
        cout<<d[i]<<' ';
    return 0;
}