Shared code

#include<bits/stdc++.h>
using namespace std;
#define int long long int        //10^-18 - 10^18
// #define ll long long int
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define ub upper_bound
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
const int mod = 1e9+7;
const long long inf = 1e18;
//const int mod = 998244353;
struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15;  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};
long long binpow(long long a, long long b) {long long res = 1;while (b > 0) {if (b & 1)res = ((res%mod)*(a%mod))%mod;a = ((a%mod)*(a%mod))%mod;b >>= 1;}return res%mod;}
int mod_add(int a, int b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;}
int mod_mul(int a, int b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;}
int mod_sub(int a, int b) {a = a % mod; b = b % mod; return (((a - b) % mod) + mod) % mod;}
// int mod_div(int a, int b) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
int mod_div(int a,int b) {a = a % mod; b = b % mod; return (mod_mul(a,binpow(b, mod-2)) + mod) % mod;}
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
const int MAX_SIZE = 1000001;
vector<int>isprime(MAX_SIZE , true);
vector<int> idx(MAX_SIZE);
vector<int> prime;
vector<int>SPF(MAX_SIZE);
void manipulated_seive(int N) {isprime[0] = isprime[1] = false ;for (int i = 2; i < N ; i++) {if (isprime[i]) {prime.push_back(i);SPF[i] = i;}for (int j = 0; j < (int)prime.size() && i * prime[j] < N && prime[j] <= SPF[i]; j++) {isprime[i * prime[j]] = false;SPF[i * prime[j]] = prime[j] ;}} for (int i = 0; i < (int)prime.size(); i++) {idx[prime[i]] = i + 1;}}
vector<int> primeFactors(int n) {vector<int> factors;while (n > 1) {factors.push_back(SPF[n]);n /= SPF[n];}return factors;}
int lg[200005];
int st[200005][31];
void generate(int n,vector<int>&arr){for(int i = 0; i < n; i++){st[i][0] = arr[i];}for(int j = 1; j <= 25; j++){for(int i = 0; i+(1ll<<j) <= n ; i++){st[i][j] = min(st[i][j-1],st[i+(1ll<<(j-1))][j-1]);}}lg[1] = 0;for(int i = 2; i<  200005; i++){lg[i] = lg[i/2]+1;}}
int getmax(int i, int j){ int L = i; int R = j;j = lg[R - L + 1];int maxm = min(st[L][j], st[R - (1 << j) + 1][j]);return maxm;}
vector<int> fac;
void initfact(int n, int p = pow(10, 9) + 7){fac.resize(n + 1);fac[0] = 1;for (int i = 1; i <= n; i++)fac[i] = (fac[i - 1] * i) % p;}
unsigned long long nCrModPFermat(unsigned long long n,int r, int p){if (n < r)return 0;if (n == 0 && r == 0)return 1;if (n == 0)return 0;if (r == 0)return 1;return (fac[n] * mod_div(fac[r], p) % p * mod_div(fac[n - r], p) % p) % p;}
map<int,int> mapm;
int fn,bn;
 
void solve(){
	int n,m;
	cin>>n>>m;
	vector<pair<int,int>> adj[n+1];
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		adj[x].push_back({y,z});
		adj[y].push_back({x,z});
	}
	set<pair<int,int>> s;
	s.insert({0,1});
	vector<int> dist(n+1,1e18);
	dist[1]=0;
	while(s.size()){
		auto it=*s.begin();
		int node=it.second;
		int dis=it.first;
		s.erase(it);
		for(auto x:adj[node]){
			int curr=x.first;
			int wt=x.second;
			if(dis+wt<dist[curr]){
				pair<int,int> p={dist[curr],curr};
				if(s.find(p)!=s.end()){
					s.erase(p);
				}
				dist[curr]=dis+wt;
				s.insert({dist[curr],curr});
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dist[i]<<" ";
	}
	cout<<endl;
}
 
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// initfact(300000,mod);
	cout << fixed;
	int t=1;
	// cin >> t;
	int tt=t;
	while(t--){
		// cout<<"Case #"<<(tt-t)<<":"<<" ";
		solve();
	}
	return 0;
}