#include <vector>
#include <fstream>
#include <climits>

#define NMAX 50010
using std::vector;

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

struct Arc {
    int node, cost;

    Arc() {
    }

    Arc(int node, int cost) {
        this->node = node;
        this->cost = cost;
    }
};

inline bool operator<(Arc x, Arc y) {
    return x.cost < y.cost;
}

int n, m;
vector<Arc> ad[NMAX];

int hash[NMAX];
bool vis[NMAX];

class Heap {
private:
    int size = 0;
    Arc heap[NMAX];

    void swap(int x, int y) {
        Arc aux = heap[x];
        heap[x] = heap[y];
        heap[y] = aux;

        hash[heap[x].node] = x;
        hash[heap[y].node] = y;
    }

    inline int parent(int node) {
        return node >> 1;
    }

    inline int left(int node) {
        return node << 1;
    }

    inline int right(int node) {
        return (node << 1) + 1;
    }

    void heapify(int node) {
        int l = left(node);
        int r = right(node);

        int min = node;
        if (l <= size && heap[l] < heap[min])
            min = l;
        if (r <= size && heap[r] < heap[min])
            min = r;

        if (min != node) {
            swap(node, min);
            heapify(min);
        }
    }

public:
    Heap() {
        size = 0;
    }

    inline Arc top() {
        return heap[1];
    }

    Arc pop() {
        Arc min = heap[1];
        heap[1] = heap[size--];
        hash[heap[1].node] = 1;
        heapify(1);
        return min;
    }

    void update(int node, Arc key) {
        heap[node] = key;
        hash[key.node] = node;

        while (node > 1 && heap[node] < heap[parent(node)]) {
            swap(node, parent(node));
            node = parent(node);
        }
    }

    void push(Arc key) {
        heap[++size] = key;
        update(size, key);
    }

    inline bool empty() {
        return !size;
    }
};

Heap pq;
int dp[NMAX];

int main() {
    int x, y, z;

    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> z;
        ad[x].push_back(Arc(y, z));
    }

    for (int i = 2; i <= n; i++)
        dp[i] = INT_MAX;

    pq.push(Arc(1, 0));
    while (!pq.empty()) {
        int node = pq.pop().node;
        if (vis[node])
            continue;

        vis[node] = true;
        for (Arc arc : ad[node])
            if (dp[node] + arc.cost < dp[arc.node]) {
                dp[arc.node] = dp[node] + arc.cost;
                if (!hash[arc.node])
                    pq.push(Arc(arc.node, dp[arc.node]));
                else
                    pq.update(hash[arc.node], Arc(arc.node, dp[arc.node]));
            }
    }

    for (int i = 2; i <= n; i++)
        if (dp[i] != INT_MAX)
            fout << dp[i] << ' ';
        else
            fout << "0 ";
    fout << '\n';

    fout.close();
    return 0;
}