дейкстра

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

mt19937 rnd(time(0));

#define ioss ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("sum.in", "r", stdin); freopen("sum.out", "w", stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

template<class T>
ll upmax(T &a, T b) { return (b > a) ? a = b, 1 : 0; }

template<class T>
ll upmin(T &a, T b) { return (b < a) ? a = b, 1 : 0; }


const ll inf = 1e18 + 7;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pair<ll, ll>>> graph(n, vector<pair<ll,ll>> ());
    for(int i = 0; i < m; i += 1){
        ll x, y, w;
        cin >> x >> y >> w;
        x--,y--;
        graph[x].pb({y, w});
        graph[y].pb({x, w});
    }
    vector<ll> dist(n, inf);
    set<pair<ll,ll>> st;
    st.insert({0, 0});
    dist[0] = 0;
    while(!st.empty()) {
        auto v = *st.begin();
        st.erase(v);
        for (auto [to, w]: graph[v.second]) {
            if (dist[to] > dist[v.second] + w) {
                st.erase({dist[to], to});
                dist[to] = dist[v.second] + w;
                st.insert({dist[to], to});
            }
        }
    }
    for(auto i : dist){
        cout << i << ' ';
    }
    cout << '\n';
}


signed main() {
    // ioss
    // file
    // (a += b) -> return value
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    // printf("Time taken: %.10fs\n", (double)(clock() - CLOCK_START)/CLOCKS_PER_SEC);
    return 0;
}