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

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 < student > 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 , 0});
    pasi[1] = 0;
    vis[1] = 1;
    
    for(int i=1;i<=n;i++){
        
        int nod = q.front().nod , cost = q.front().cost;
        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 , pasi[vecin.nod]});
            }
        }
        
        
    }
    
    for(int i=2;i<=n;i++){
        fout<<pasi[i]<<" ";
    }
    
    
    
}