#include <bits/stdc++.h>

using namespace std;

FILE *fin = fopen("dijkstra.in", "r");
FILE *fout = fopen("dijkstra.out", "w");

#define BUF 1 << 17
char buf[BUF];
int pos = BUF;

inline char next()  {
    if(pos == BUF)
        fread(buf, 1, BUF, fin), pos = 0;
    return buf[pos++];
}

inline int read()  {
    int x = 0;
    char ch = next();
    while(!isdigit(ch))
        ch = next();
    while(isdigit(ch))
        x = x * 10 + ch - '0', ch = next();
    return x;
}

int N, M;

struct edge  {
    int vec;
    int cost;
    bool operator < (const edge &a) const {
        return cost > a.cost;
    }
};

#define MAX_N 50001
#define MAX_M 250001

vector <edge> v[MAX_N];
priority_queue <edge> q;
int d[MAX_N];

inline void dijkstra(int);

int main()  {
    N = read(), M = read();
    for(int i = 1;i <= M;i++)  {
        int a, b, c;
        a = read(), b = read(), c = read();
        v[a].push_back({b, c});
    }
    dijkstra(1);
    for(int i = 2;i <= N;i++)
        if(d[i] == INT_MAX)
            fprintf(fout, "0 ");
        else
            fprintf(fout, "%d ", d[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}

inline void dijkstra(int sursa)  {
    q.push({sursa, 0});
    for(int i = 0;i <= N;i++)
        d[i] = INT_MAX;
    while(!q.empty())  {
        edge aux;
        aux = q.top();
        q.pop();
        int nod = aux.vec, cost = aux.cost;
        if(d[nod] == INT_MAX)  {
            d[nod] = cost;
            for(int i = 0;i < v[nod].size();i++)
                if(d[v[nod][i].vec] == INT_MAX)
                    q.push({v[nod][i].vec, v[nod][i].cost + cost});
        }
    }
}