#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct str{
    int nod,cost;
    bool operator < (const str & aux) const {
        return cost>aux.cost;
    }
};
int n,p,m;
vector<int>d;
vector<vector<pair<int,int>>>a;
priority_queue<str> pq;

void dijkstra(){
    d[1]=0;
    pq.push({1,0});
    while(!pq.empty()){
        int nod=pq.top().nod,cost=pq.top().cost;
        pq.pop();
        if(cost>d[nod]) continue;
        for(auto f:a[nod]){
            if(d[nod]+f.second<d[f.first]){
                d[f.first]=d[nod]+f.second;
                pq.push({f.first,d[f.first]});
            }
        }
    }
}

int main(){
    d.resize(50005);
    fill(d.begin(),d.end(),INT_MAX-1);
    fin>>n>>m;
    a.resize(n+1);
    int x,y,k;
    for(int i=0;i<m;i++){
        fin>>x>>y>>k;
        a[x].push_back({y,k});
    }
    dijkstra();
    for(int i=2;i<=n;i++){
        if(d[i]!=INT_MAX-1) fout<<d[i]<<" ";
        else fout<<"0 ";
    }
    return 0;
}

/**
5 4 6
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2
**/