# include <bits/stdc++.h>
# define MOD 666013
# define NR 50005
# define INF 999999999
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct edgeNode;
struct node;
struct heapNode;

struct heapNode {
    int dist;
    node* nod;
};

struct edgeNode {
    int cost;
    node* nod;
};

struct node {
    int label;
    vector<edgeNode> edges;
};

vector <heapNode> HEAP;
vector <node*> HASH[MOD];

node* getNode (int label) {
    int key = label % MOD;

    for (int i=0; i<HASH[key].size(); ++i)
        if (HASH[key][i]->label == label)
            return HASH[key][i];

    return NULL;
}


int VV, n, m, x, y, cost;
int Distance[NR];

void addHeap(int label) {
    heapNode hnod;
    hnod.dist = Distance[label];
    hnod.nod = getNode(label);

    HEAP.push_back(hnod);
    int position = HEAP.size()-1;

    while (position > 1 && HEAP[position].dist < HEAP[position/2].dist) {
        swap(HEAP[position], HEAP[position/2]);
        position = position/2;
    }
}

void removeHeap () {
    int nHeap = HEAP.size()-1;

    swap(HEAP[1], HEAP[nHeap]);
    HEAP.pop_back(); --nHeap;

    int position = 1;

    do {
        int son = 0;
        if (2*position <= nHeap)
            son = 2*position;

        if (2*position+1 <= nHeap && HEAP[2*position+1].dist < HEAP[2*position].dist)
            son = 2*position+1;

        if (son!=0 && HEAP[position].dist > HEAP[son].dist) {
            swap(HEAP[position], HEAP[son]);
            position = son;
        } else {
            break;
        }
    } while (true);
}

void djikstra() {
    addHeap(1);
    addHeap(1);

    while (HEAP.size() != 1) {
        int dist = HEAP[1].dist;
        node* nod = HEAP[1].nod;

        removeHeap();

        if (dist != Distance[nod->label]) continue;

        for (auto &x: nod->edges) {
            if (dist + x.cost < Distance[(x.nod)->label]) {
                Distance[(x.nod)->label] = dist + x.cost;
                addHeap((x.nod)->label);
            }
        }
    }
}

int main () {
    f>>n>>m;

    // we have to build the node is the memory
    // and insert them in the hashmap

    for (int i=1; i<=n; ++i) {
        node* nod = new node();

        nod->label = i;
        (nod->edges).clear();

        HASH[i % MOD].push_back(nod);
    }

    for (int i=1; i<=m; ++i) {
        f>>x>>y>>cost;

        edgeNode edge;
        edge.cost = cost;
        edge.nod = getNode(y);

        node* nod = getNode(x);
        (nod->edges).push_back(edge);
    }

    Distance[1] = 0;
    for (int i=2; i<=n; ++i) {
        Distance[i] = INF;
    }

    djikstra();

    for (int i=2; i<=n; ++i) {
        g<<Distance[i]<<" ";
    }
    g<<"\n";

    return 0;
}