#include <iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;
const int N=50005;
const int oo=1<<30;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair <int,int>> q[N];
int n,m,c[N];
priority_queue <pair <int,int>,vector <pair<int,int>>,greater<pair<int,int>>>H;
int main()
{fin>>n>>m;
for(int i=1;i<=n;++i)
    c[i]=oo;
    for(int x,y,ccost,i=0;i<m;++i){
        fin>>x>>y>>ccost;
    q[x].push_back(make_pair(y,ccost));}
    H.push(make_pair(0,1));
    c[1]=0;
    while(H.size())
    {
        int cost=H.top().first;
        int x=H.top().second;
        H.pop();
        if(cost>c[x])
            continue;
        for(int i=0;i<q[x].size();++i)
            if(c[q[x][i].first]>cost+q[x][i].second)
            {
                c[q[x][i].first]=cost+q[x][i].second;
                H.push(make_pair(cost+q[x][i].second,q[x][i].first));
            }
    }
    for(int i=2;i<=n;++i)
        if(c[i]==oo)
        fout<<0;
    else
        fout<<c[i]<<" ";
    return 0;
}