#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;

inline char nextch(void) {
    static int buff = BMAX;

    if(buff == BMAX) {
        buff = 0;
        fread(buck, 1, BMAX, stdin); }

    return buck[buff++]; }

inline void get(int &arg) {
    char ch;

    do {
        ch = nextch(); }
    while(ch < '0' || ch > '9');
    arg = ch - '0';

    while(true) {
        ch = nextch();
        if(ch < '0' || ch > '9')
            return;
        arg = arg * 10 + ch - '0'; } }

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;

    get(n), get(m);
    for(int i=1; i<=m; ++i) {
        get(u), get(v), get(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; }