//#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int,int> > v[50005];
priority_queue<pair<int,int> > q;
bool f[50005];
long long d[50005];
int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int n,m,x,y,cost;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    for(int i=1;i<=n;i++)
        d[i]=20000*50000+5;
    ///we will see distance from 1 to any node
    q.push(make_pair(0,1));
    d[1]=0;
    while(q.empty()==false){
        x=q.top().second;
        y=q.top().first;
        q.pop();
        if(f[x]==0){
            f[x]=1;
            //cout<<y<<" "<<x<<"\n";
            for(int i=0;i<v[x].size();i++){
                if(f[v[x][i].first]==0){
                    if(-y+v[x][i].second<d[v[x][i].first]){
                        d[v[x][i].first]=-y+v[x][i].second;
                        //cout<<d[v[x][i].first]<<"\n";
                        q.push(make_pair(-d[v[x][i].first],v[x][i].first));
                    }
                }
            }
        }
    }
    for(int i=2;i<=n;i++)
        cout<<d[i]<<" ";
    return 0;
}
/*
q (-q,1)
x=1
y=0
f[1,0,0,0,0]
d[0,1,0,0,0]
(2,1) (4,2)
(3,2)
(5,6)
(3,4) (4,3)
*/