q013.rs

// from scratch is: 
// https://gist.github.com/tokugh/ba6abbf56482e222cdf06d3148b24c45
use petgraph::{prelude::*, graph::node_index};
use petgraph::algo::dijkstra;
use proconio::{input, fastout};

#[fastout]
fn main() {
	input! { n: usize, abc: [(u32, u32, i32)], };
	let mut g = UnGraph::<(), i32>::from_edges(abc);

	let node1 = node_index(1);
	let dist1 = dijkstra(&g, node1, None, |c| *c.weight());
	let nodeN = node_index(n);
	let distN = dijkstra(&g, nodeN, None, |c| *c.weight());

	let mut ans = vec![0; n+1];
	for (node, dist) in dist1.iter().chain(distN.iter()) {
		ans[node.index()] += dist;
	}

	for i in 1..=n {
		println!("{}", ans[i]);
	}
}