#include <iostream>
#include <bits/stdc++.h>

using namespace std;
ifstream r("dijkstra.in");
ofstream w("dijkstra.out");
struct call{
    int nod;
    long long cost;
    call(int nod, long long cost){
        this->nod=nod;
        this->cost=cost;
    }
    bool operator<(call b) const{
        return cost>b.cost;
    }
};
vector<call>g[50001];
long long v[50001];
priority_queue<call>q;
int main()
{
    int n, m;
    r>>n>>m;
    for(int i=0;i<m;i++){
        int x, y, c;
        r>>x>>y>>c;
        g[x].push_back(call(y, c));
    }
    v[1]=-1;
    q.push(call(1, 0));
    while(q.size()!=0){
        int a=q.top().nod;
        long long sum=q.top().cost;
        if(v[a]==0){
            v[a]=sum;
        }
        q.pop();
        for(int i=0;i<g[a].size();i++){
            if(v[g[a][i].nod]==0){
                q.push(call(g[a][i].nod, sum+g[a][i].cost));
            }
        }
    }
    for(int i=2;i<=n;i++){
        w<<v[i]<<" ";
    }
    return 0;
}