//BFS --------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100005, INF = 999999;

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

int n, m, x, y, c, vis[nmax], pasi[nmax];

typedef struct poz{
    int nod, cost;
}student;

vector < student > adj[nmax];
queue < int > q;


int main()
{
    
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        adj[x].push_back({y , c});
    }
    
    
    for(int i=1;i<=n;i++){
        pasi[i] = INF;
    }
    
    q.push(1);
    pasi[1] = 0;
    vis[1] = 1;
    
    while(!q.empty()){
        
        int nod = q.front();
        q.pop();
        
        for(auto vecin : adj[nod]){
            if(vis[vecin.nod] == 0 && pasi[nod] + vecin.cost < pasi[vecin.nod]){
                
                pasi[vecin.nod] = pasi[nod] + vecin.cost;
                vis[vecin.nod] = 1;
                q.push(vecin.nod);
                
            }
        }
        
        
    }
    
    for(int i=2;i<=n;i++){
        fout<<pasi[i]<<" ";
    }
    
    
    
}