#include <bits/stdc++.h>
#define InFile "dijkstra.in"
#define OutFile "dijkstra.out"
#define DMAX 50010

using namespace std;

FILE *fin=fopen(InFile,"r");
FILE *fout=fopen(OutFile,"w");

struct Arc
       {int node;
        int cost;
       };

inline bool operator<(Arc x, Arc y) {
    return x.cost > y.cost;
}

int n, m;
vector <Arc> ad[DMAX];

int dp[DMAX];
bool onPQ[DMAX];
priority_queue <Arc> pq;

int main()
{int a, b, c;
 int i, node;
 fscanf(fin,"%d %d\n", &n, &m);
 for(i = 0; i < m; i++) {
     fscanf(fin,"%d %d %d\n", &a, &b, &c);
     ad[a].push_back({b, c});
    }
 pq.push({1, 0});
 onPQ[1] = true;
 while (!pq.empty()) {
        node = pq.top().node;
        pq.pop();
        onPQ[node] = false;
        for(i=0;i<ad[node].size();i++) {
            if (!dp[ad[node][i].node] || dp[node] + ad[node][i].cost < dp[ad[node][i].node]) {
                dp[ad[node][i].node] = dp[node] + ad[node][i].cost;
                if (!onPQ[ad[node][i].node]) {
                    pq.push({ad[node][i].node, dp[ad[node][i].node]});
                    onPQ[ad[node][i].node] = true;
                    }
                }
            }
        }
 for (i = 2; i <= n; i++)
      fprintf(fout,"%d ", dp[i]);
 fprintf(fout,"\n");
 return 0;
}