#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

const int MAX_N = 50000;
const int INF = -1;

using namespace std;

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

class Node {
public:
    int v, c;

    Node(int a = 0, int b = 0) {
        v = a;
        c = b;
    }

    bool operator < (const Node other) const {
        return this ->c > other.c;
    }
};

int n, m;
int dist[MAX_N + 5];
bitset<MAX_N + 5> vis;
vector<Node> G[MAX_N + 5];
priority_queue<Node> pq;

void dijkstra() {
    for(int i = 1; i <= n; i++)
        dist[i] = INF;
    vis.reset();
    dist[1] = 0;
    pq.push(Node(1, 0));

    while(!pq.empty()) {
        while(!pq.empty() && vis[pq.top().v] == 1)
            pq.pop();
        if(pq.empty())
            break;
        Node u = pq.top();
        vis[u.v] = 1;
        pq.pop();
        for(auto v : G[u.v])
            if(!vis[v.v])
            if((u.c + v.c < dist[v.v]) || (dist[v.v] == -1)) {
                dist[v.v] = u.c + v.c;
                pq.push(Node(v.v, dist[v.v]));
            }
    }
}
int main() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        G[a].push_back(Node(b, c));
    }

    dijkstra();

    for(int i = 2; i <= n; i++)
        if(dist[i] == -1)
            fout << 0 << ' ';
        else fout << dist[i] <<' ';

    return 0;
}