#include <cassert>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
 
const int NMAX = 50005,
          MMAX = 250005,
          BMAX = 1 << 16;
 
struct EDGE {
    int v, w;
 
    bool operator < (const EDGE &arg) const {
        return (w == arg.w) ? (v < arg.v) : (w < arg.w); } };
 
struct NOD {
    int n, w; };
 
 
int dist[NMAX];
char buck[BMAX];
vector<EDGE> g[NMAX];
set<EDGE> roads;

void dijkstra(int nod) {
    memset(dist, 0xFF, sizeof(dist));
    EDGE road;
 
    roads.insert({nod, 0});
    dist[nod] = 0;
 
    while(!roads.empty()) {
        nod = roads.begin()->v;
        roads.erase(roads.begin());
 
        for(auto &i: g[nod]) {
            road.v = i.v;
            road.w = dist[nod] + i.w;
 
            if(dist[road.v] == -1) {
                dist[road.v] = road.w;
                roads.insert(road); }
            else if(road.w < dist[road.v]){
                roads.erase({road.v, dist[road.v]});
                dist[road.v] = road.w;
                roads.insert(road); } } } }
 
int main(void) {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n, m, u, v, w;
 
	scanf("%d%d", &n, &m);
    for(int i=1; i<=m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w}); }
 
    for(int i=1; i<=n; ++i)
        sort(g[i].begin(), g[i].end());
 
    dijkstra(1);
 
    for(int i=2; i<=n; ++i)
        printf("%d ", (dist[i] != -1) ? dist[i] : 0);
    printf("\n");
 
    return 0; }