#include <fstream>
#include <vector>
#include <cstdio>
#define INF (int) 1e9+7;

using namespace std;
vector <int> g[30010];
vector <int> w[30010];
int n, m, a, b, u, v, s, size, j;
int q[30010], d[30010], used[30010];

void swap(int a, int b) {
    int c = a;
    a = b;
    b = c;
}

void siftDown(int i) {
    while (2 * i + 1 < size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        j = left;
        if (right < size && q[right] < q[left])
            j = right;
        if (q[i] <= q[j])
            break;
        swap(q[i], q[j]);
        i = j;
    }
}

void siftUp(int i) {
    while (q[i] < q[(i - 1) / 2])
        swap(q[i], q[(i - 1) / 2]);
        i = (i - 1) / 2;
}

void insert (int k) {
    size++;
    q[size - 1] = k;
    siftUp(size - 1);
    used[k] = true;
}

int extractMin() {
    int min = q[0];
    q[0] = q[size - 1];
    size--;
    siftDown(0);
    return min;
}

int main() {
    ifstream in("pathbgep.in");
    ofstream out("pathbgep.out");
    in >> n >> m;
    for (int i = 1; i <= n; i++) {
        used[i] = false;
        d[i] = INF;
    }

    for (int i = 0; i < m; i++) {
        in >> a >> b >> v;
        g[a].push_back(b);
        g[b].push_back(a);
        w[a].push_back(v);
        w[b].push_back(v);
    }

    s = 1;
    d[s] = 0;
    size = 0;
    insert(s);
    while(size != 0) {
        u = extractMin();
        int  l = g[u].size();
        for (int i = 0; i < l; i++)
            if (d[g[u][i]] > d[u] + w[u][i]){
                d[g[u][i]] = d[u] + w[u][i];
                if (!used[g[u][i]])
                    insert(g[u][i]);
            }
    }

    for (int i = 1; i <= n; i++)
        out << d[i] << ' ';

    return 0;
}