dijkstra_using_priority_queue

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define mod 1000000007
#define N 10000006
#define all(x) (x).begin(),(x).end()
#define LL_INF (1LL << 62)
#define INF (1 << 30)
#define SetBit(x, k) (x |= (1LL << k))
#define ClearBit(x, k) (x &= ~(1LL << k))
#define CheckBit(x, k) ((x>>k)&1)
const int mx=2e6+12;
ll fact[N];
ll powerMod(ll a, ll b){
    if(b==0) return 1;

    if(b%2==0){
        ll x = powerMod(a, b/2);
        return (x*x)%mod;
    }
    else {
        ll x = powerMod(a, b/2);
        return ((x*x)%mod * a)%mod;
    }

    return 0;
}

ll inverseMod(ll a){
    return powerMod(a, mod-2);
}

ll nCrMod(ll n, ll r){
    if (r == 0)
        return 1;
    if (r > n)
        return 0;

    return (fact[n] * inverseMod((fact[r] * fact[n - r]) % mod)) % mod;
}
void factorial(){
fact[0] = 1;
    for(int i = 1; i < N; i++){
        fact[i] = (fact[i-1]*i)%mod;
}}


// Coding starts from here...
vector<pair<int,ll>>adj[mx];


int main()
{
  ios::sync_with_stdio(false);cin.tie(0);
  int n,m;cin>>n>>m;
  for(int i=1;i<=m;i++){
    ll u,v,w;
    cin>>u>>v>>w;
    adj[u].push_back({v,w});
    adj[v].push_back({u,w});
  }

  ll dis[n+1];
  for(int i=1;i<=n;i++)dis[i]=LL_INF;
  int src=1;
  dis[src]=0;


  priority_queue<pair<ll,int>>pq;
  pq.push({0,src});
  while(!pq.empty()){
    auto x=pq.top();
    pq.pop();

    ll d=-x.first;
    int nd=x.second;
    if(dis[nd]<d)continue;

    for(auto u:adj[nd]){
        int v=u.first;
        ll w=u.second;
        if(dis[v]>d+w){
            dis[v]=d+w;
            pq.push({-dis[v],v});
        }
    }
  }

    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";cout<<endl;




  return 0;
}