#include <stdio.h>
#include <ctype.h>
#include <limits.h>
#include <vector>
#include <queue>

using namespace std;

FILE *fin = fopen("dijkstra.in", "r"), *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, semn = 1;
    char ch = next();
    while(!isdigit(ch) && ch != '-')
        ch = next();
    if(ch == '-')
        ch = next(), semn = -1;
    while(isdigit(ch))
        x = x * 10 + ch - '0', ch = next();
    return x;
}

int N, M;

#define NMAX 50000

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

int d[NMAX + 1];
vector <much> v[NMAX + 1];
priority_queue <much> pq;

inline void dijkstra(int nod)  {
    for(int i = 0;i <= N;i++)
        d[i] = INT_MAX;
    pq.push({nod, 0});
    while(!pq.empty())  {
        much vec = pq.top();
        pq.pop();
        if(d[vec.vec] == INT_MAX)  {
            d[vec.vec] = vec.cost;
            for(auto &x: v[vec.vec])  {
                if(d[x.vec] == INT_MAX)  {
                    pq.push({x.vec, x.cost + vec.cost});
                }
            }
        }
    }
}

int main()  {
    N = read(), M = read();
    for(int i = 0;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++)
        fprintf(fout, "%d ", (d[i] == INT_MAX) ? 0 : d[i]);
    fputc('\n', fout);
    fclose(fin);
    fclose(fout);
    return 0;
}