#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct Node{
    int vecin;
    int cost;

    Node(int vecin,int cost){
        this->vecin=vecin;
        this->cost=cost;
    }
};

list<Node> adj[50001];
vector<long> dist;
set<pair<int,int> > nextStep;
int n,m,a,b,c;

int main()
{
    fin>>n>>m;
    dist.resize(n+1);
    fill(dist.begin(),dist.end(),LONG_MAX);
    for(int i=0;i<m;i+=1){
        fin>>a>>b>>c;
        adj[a].push_back(Node(b,c));
    }
    fin.close();
    dist[1]=0;
    nextStep.insert(make_pair(0,1));
    while(nextStep.size()){
        int x = nextStep.begin()->second;
        nextStep.erase(nextStep.begin());
        for(list<Node>::iterator it=adj[x].begin();it!=adj[x].end();it++){
            if(dist[it->vecin]>dist[x]+it->cost){
                dist[it->vecin]=dist[x]+it->cost;
                nextStep.insert(make_pair(dist[it->vecin],it->vecin));
            }
        }
    }
    for(int i=2;i<=n;i+=1)
        fout<<(dist[i]==LONG_MAX ? 0:dist[i])<<' ';
    return 0;
}