#include <iostream>
#include <climits>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int NMax = 5e4 + 5;

int N,M;
int dist[NMax];
bool found[NMax];
// dist[i] = distanta minima de la nodul 1 la nodul i
// found[i] = true daca s-a gasit dist[i]

struct elem {
    int dest,cost;
    elem() {
        elem(0,0);
    }
    elem(int a,int b) {
        dest = a;
        cost = b;
    }
};
bool operator <(elem a, elem b) {
    return a.cost>b.cost;
}

vector<elem> v[NMax];
// lista de adiacenta

priority_queue<elem> h;
// heap ce determina muchia minima de la subgraful curent la un nod din afara subgrafului

int main() {
    in>>N>>M;

    for (int i=1;i<=N;++i) {
        dist[i] = INT_MAX;
    }

    for (int i=1;i<=M;++i) {
        int x,y,c;
        in>>x>>y>>c;
        elem m(y,c);
        v[x].push_back(m);
    }

    elem st(1,0);
    h.push(st);
    dist[1] = 0;
    while (h.size()) {
        st = h.top();
        h.pop();
        int nod = st.dest,cost = st.cost;
        if (cost > dist[nod]) {
            continue;
        }
        found[nod] = true;

        int siz = v[nod].size();
        for (int k=0;k<siz;++k) {
            int next = v[nod][k].dest, val = v[nod][k].cost;
            if (!found[next] && dist[next] > dist[nod] + val) {
                dist[next] = dist[nod] + val;
                elem n(next,dist[next]);
                h.push(n);
            }
        }
    }

    for (int i=2;i<=N;++i) {
        int o = (dist[i]!=INT_MAX) ? dist[i] : 0;
        out<<o<<' ';
    }

    in.close();out.close();
    return 0;
}