q049.rs

use petgraph::prelude::*;
use petgraph::algo::{min_spanning_tree, connected_components};
use petgraph::data::FromElements;

fn main() {
  proconio::input!{ n: usize, m: usize, clr: [(i64, usize, usize); m], };
  let lrc: Vec<_> = clr.into_iter().map(|(c, l, r)| (l-1, r, c)).collect();
  let g = UnGraph::<(), _, _>::from_edges(&lrc);
  if g.node_count() < n+1 || connected_components(&g) > 1 { println!("-1"); return; }
  let mst = UnGraph::<_, _>::from_elements(min_spanning_tree(&g));
  let ans: i64 = mst.edge_references().map(|e|*e.weight()).sum();
  println!("{}", ans);
}