#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
//#define fin cin
//#define fout cout
const int nax = 5e5+2;
//const int64_t inf = 1e17;
const int inf = 1e9+2;

int n,m,p;
int y,x,w;

void dijkstra(int node){
    fin>>n>>m;
    vector<pair<int,int>> G[n+1];
    for(int i=1;i<=m;i++){
        fin>>x>>y>>w;
        G[x].push_back({y,w});
    }
    bitset<nax> vis;
    priority_queue<pair<int,int>> H;
    vector<int> cmin(n+1,inf);
    cmin[1]=0;
    vis[node]=true;
    H.push({0,node});
    while(!H.empty()){
        int dist = - H.top().first;
        int x = H.top().second;
        H.pop();
        for(pair<int,int> it:G[x]){
            if(cmin[it.first] > cmin[x] + it.second && !vis[it.first]){
                cmin[it.first] =  cmin[x] + it.second;
                vis[it.first]=true;
                H.push({-cmin[it.first],it.first});
            }
        }
    }
    for(int i=2;i<=n;i++)
        fout<<cmin[i]<<' ';
}

int main(){
    dijkstra(1);

    return 0;
}