#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
typedef signed long long ll;
typedef unsigned int uint;
typedef unsigned char uchar;
template <typename T>
void printarray(T v[], uint n) {for(uint i = 0; i < n; i ++){cout << v[i] << " ";}cout << endl;}
template <typename T>
void printvector(vector<T> v){for (uint i = 0; i < v.size(); i ++){cout << v[i] << " ";}cout << endl;}
#define dbg(x) cout << #x " = " << x << " | ";
#define dbgnl(x) cout << #x " = " << x << endl;

const int nmax = 50005;
struct edge_t {
    int finish, dist;
};
vector<edge_t> G[nmax];
int n, m;

void read() {
    cin>>n>>m;
    for (int i =0;i < m; ++i) {
        int s,f,d;
        cin >>s>>f>>d;
        G[s-1].push_back({f-1, d});
    }
}

struct node_dist_t {
    int node, dist;
    bool operator>(const node_dist_t& rhs) const {
        return dist < rhs.dist;
    }
};
priority_queue<node_dist_t, vector<node_dist_t>, greater<node_dist_t>> pq;
int dists[nmax];
const int INF = 10e6;
bitset<nmax> visited;

void solve() {
    for (int i = 0; i < n; ++i) {
        dists[i] = INF;
    }
    dists[0] = 0;

    pq.push({0, dists[0]});
    while (!pq.empty()) {
        auto nd = pq.top();
        pq.pop();
        int node = nd.node;
        int dist = nd.dist;

        if (visited[node]) continue;
        visited[node] = true;

        for (auto edge: G[node]) {
            int new_dist = dist + edge.dist;
            if (dists[edge.finish] > new_dist) {
                dists[edge.finish] = new_dist;
                if (!visited[edge.finish]) {
                    pq.push({edge.finish, new_dist});
                }
            }
        }
    }
}

void write() {
    for (int i = 1; i < n; i++) {
        cout << dists[i] << " ";
    }
    cout << "\n";
}

int main() {
    freopen("dijkstra.in", "r", stdin); 
    freopen("dijkstra.out", "w", stdout); 
      
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    read();
    solve();
    write();

    return 0;
}