---
tags: codebook
---
# dijkstra

#include<iostream>
#include<limits>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
template<typename T>
struct dijkstra{
	struct node{
		size_t b;T d;
		node(const size_t& x,const T& y):b(x),d(y){}
		friend bool operator<(const node& a,const node& b){return a.d>b.d;}
	};
	vector<T> d;vector<bool> visit;vector<size_t> parent;
	const T& operator[](const size_t& x){return d[x];}
	dijkstra(const vector<vector<node>>& v,const size_t& x=0)
	:d(v.size(),numeric_limits<T>::max()),visit(v.size(),false),parent(v.size()){
		priority_queue<node> pq;
		d[x]=0,parent[x]=x,pq.emplace(x,d[x]);
		for(size_t i=0;i!=v.size();i++){
			size_t a=numeric_limits<size_t>::max();
			do a=pq.top().b,pq.pop();while(!pq.empty()&&visit[a]);
			if(a==numeric_limits<size_t>::max()){break;}visit[a]=true;
			for(const auto& b:v[a])
				if(!visit[b.b]&&d[a]+b.d<d[b.b])
					parent[b.b]=a,pq.emplace(b.b,d[b.b]=d[a]+b.d);
		}
	}
};using node=dijkstra<long long>::node;
ostream& operator<<(ostream& os,const vector<T>& v){
    for(const auto& i:v){os<<i<<' ';}return os;}
int main(){
	size_t n,a,b;long long c;cin>>n;
	vector<vector<node>> v(n);
	for(size_t i=1;i!=n;i++)
		cin>>a>>b>>c,v[a-1].emplace_back(b-1,c),v[b-1].emplace_back(a-1,c);
	dijkstra<long long> tree(v);
	cout<<tree.d<<endl;
	return 0;
}

#include<iostream>
#include<limits>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
template<typename T>
struct dijkstra {
	constexpr size_t inf_distance = -1;
	struct node {
		size_t b; T d;
		node(const size_t& x, const T& y): b(x), d(y) {}
		friend bool operator<(const node& a, const node& b) {return a.d > b.d;}
	};
	vector<T> d; vector<bool> visit; vector<size_t> parent;
	const vector<size_t> path(const size_t& x)const {
		vector<size_t> v;
		do v.push_back(x); while (x != parent[x]);
		return v;
	}
	const T& operator[](const size_t& x)const {return d[x];}
	dijkstra(const vector<vector<node>>& v, const size_t& x = 0)
		: d(v.size(), numeric_limits<T>::max()), visit(v.size(), false), parent(v.size()) {
		priority_queue<node> pq;
		d[x] = 0, parent[x] = x, pq.emplace(x, d[x]);
		while (!pq.empty()) {
			size_t a = inf_distance;
			do a = pq.top().b, pq.pop(); while (!pq.empty() && visit[a]);
			if (a == inf_distance) break;
			visit[a] = true;
			for (const auto& b : v[a])
				if (!visit[b.b] && d[a] + b.d < d[b.b])
					parent[b.b] = a, pq.emplace(b.b, d[b.b] = d[a] + b.d);
		}
	}
};
using node = dijkstra<long long>::node;
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (const auto& i : v)
		os << i << ' ';
	return os;
}
int main() {
	size_t n, a, b; long long c; cin >> n;
	vector<vector<node>> v(n);
	for (size_t i = 1; i != n; i++)
		cin >> a >> b >> c, v[a - 1].emplace_back(b - 1, c), v[b - 1].emplace_back(a - 1, c);
	dijkstra<long long> tree(v);
	cout << tree.d << endl;
	return 0;
}