#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int,int>> v[250010];
int viz[50010],d[50010];
int n,m;
int main()
{
    fin>>n>>m;
    int x,y,w;
    while(fin>>x>>y>>w){
        v[x].push_back({y,w});
    }
    priority_queue<pair<int,int>> q;
    q.push({0,1});
    while(!q.empty()){
        int k=q.top().second;
        q.pop();
        if(viz[k]==0){
            viz[k]=1;
            for(auto a:v[k]){
                int i=a.first;
                int w=a.second;
                if(d[i]>d[k]+w || d[i]==0){
                    d[i]=d[k]+w;
                    q.push({-d[i],i});
                }
            }
        }
    }
    for(int i=2;i<=n;++i)
            fout<<d[i]<<" ";
    return 0;
}