//---------- begin union_find ----------
#[derive(Clone)]
pub struct DSU {
    p: Vec<i32>,
}
impl DSU {
    pub fn new(n: usize) -> DSU {
        assert!(n < std::i32::MAX as usize);
        DSU { p: vec![-1; n] }
    }
    pub fn init(&mut self) {
        self.p.iter_mut().for_each(|p| *p = -1);
    }
    pub fn root(&self, mut x: usize) -> usize {
        assert!(x < self.p.len());
        while self.p[x] >= 0 {
            x = self.p[x] as usize;
        }
        x
    }
    pub fn same(&self, x: usize, y: usize) -> bool {
        assert!(x < self.p.len() && y < self.p.len());
        self.root(x) == self.root(y)
    }
    pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
        assert!(x < self.p.len() && y < self.p.len());
        let mut x = self.root(x);
        let mut y = self.root(y);
        if x == y {
            return None;
        }
        if self.p[x] > self.p[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.p[x] += self.p[y];
        self.p[y] = x as i32;
        Some((x, y))
    }
    pub fn parent(&self, x: usize) -> Option<usize> {
        assert!(x < self.p.len());
        let p = self.p[x];
        if p >= 0 {
            Some(p as usize)
        } else {
            None
        }
    }
    pub fn sum<F>(&self, mut x: usize, mut f: F) -> usize
    where
        F: FnMut(usize),
    {
        while let Some(p) = self.parent(x) {
            f(x);
            x = p;
        }
        x
    }
    pub fn size(&self, x: usize) -> usize {
        assert!(x < self.p.len());
        let r = self.root(x);
        (-self.p[r]) as usize
    }
}
//---------- end union_find ----------
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let t: u32 = sc.next();
    for _ in 0..t {
        let n: usize = sc.next();
        let m: usize = sc.next();
        let mut e = vec![(0, 0, 0); m];
        for e in e.iter_mut() {
            e.0 = sc.next::<usize>() - 1;
            e.1 = sc.next::<usize>() - 1;
            e.2 = sc.next::<i64>();
        }
        let ans = solve(n, e);
        writeln!(out, "{} {}", ans[0], ans[1]).ok();
    }
}

fn solve(n: usize, mut e: Vec<(usize, usize, i64)>) -> [i64; 2] {
    e.sort_by_key(|e| e.2);
    let mut dsu = DSU::new(n);
    let mut tree = vec![];
    let mut test = vec![];
    for (a, b, c) in e {
        if dsu.unite(a, b).is_some() {
            tree.push((a, b, c));
        } else {
            test.push((a, b, c));
        }
    }
    if tree.len() + 1 != n {
        return [-1; 2];
    }
    let tree = tree;
    let s = tree.iter().map(|e| e.2).sum::<i64>();
    let mut ans = [std::i64::MAX; 2];
    ans[s as usize & 1] = s;
    let mut dsu = vec![DSU::new(n); 2];
    let mut memo = vec![];
    for (i, dsu) in dsu.iter_mut().enumerate() {
        let mut tree = tree.clone();
        for e in tree.iter_mut() {
            if e.2 % 2 != (i as i64) {
                e.2 = 0;
            }
        }
        tree.sort_by_key(|e| e.2);
        let mut dp = vec![std::i64::MAX; n];
        for (a, b, c) in tree {
            let (_, x) = dsu.unite(a, b).unwrap();
            dp[x] = c;
        }
        memo.push(dp);
    }
    let find = |mut x: usize, mut y: usize, p: usize| -> Option<i64> {
        let memo = &memo[p];
        let dsu = &dsu[p];
        let mut ans = std::i64::MAX;
        while x != y {
            if memo[x] >= memo[y] {
                std::mem::swap(&mut x, &mut y);
            }
            if memo[x] != 0 {
                ans = ans.max(memo[x]);
            }
            x = dsu.parent(x).unwrap();
        }
        if ans != std::i64::MAX {
            Some(ans)
        } else {
            None
        }
    };
    let po = &mut ans[(s as usize ^ 1) & 1];
    for (a, b, c) in test {
        if let Some(w) = find(a, b, (c as usize ^ 1) & 1) {
            *po = std::cmp::min(*po, s - w + c);
        }
    }
    if *po == std::i64::MAX {
        *po = -1;
    }
    ans
}