/*
▄███████▀▀▀▀▀▀███████▄
░▐████▀▒ЗАПУСКАЕМ▒▀██████▄
░███▀▒▒▒▒▒ДЯДЮ▒▒▒▒▒▒▀█████
░▐██▒▒▒▒▒▒БОГДАНА▒▒▒▒▒████▌
░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
░░░░▄██████████████▒▒▐▌
░░░▀███▀▀████▀█████▀▒▌
░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐
TAYA
*/
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <cassert>
#include <iomanip>
#include <random>


using namespace std;



#define ll long long
#define ld double
#define null NULL
#define prev prev228
#define index index228
#define left left228
#define right right228
#define hash hash228
#define y1 y1228
#define y0 y0228
#define firn(i, n) for (int i = 0; i < (int)n; ++i)
#define forn(i, n) for (int i = 1; i <= (int)n; ++i)
#define int long long

template<typename T> inline void uin(T &a, T b) {
    if (b < a) a = b;
}

template<typename T> inline void uax(T &a, T b) {
    if (b > a) a = b;
}

const int maxn = 507, INF = 1e18 + 7;

int n, m;


struct DSU
{
	vector<int> p, sz;

	DSU(int n) {
		p.resize(n + 3);
		sz.resize(n + 3);
		forn(i, n) {
			p[i] = i;
			sz[i] = 1;
		}
	}

	int get_p(int v) {
		if (p[v] == v) return v;
		p[v] = get_p(p[v]);
		return p[v];
	}

	void join(int u, int v) {
		u = get_p(u);
		v = get_p(v);
		if (u != v) {
			if (sz[u] < sz[v]) {
				p[u] = v;
				sz[v] += sz[u];
			} else {
				p[v] = u;
				sz[u] += sz[v];
			}
		}
	}

	bool con(int u, int v) {
		return get_p(u) == get_p(v);
	}
};

struct edge
{
	int u, v, w, id;
	edge() {}
	edge(int _u, int _v, int _w, int _id) {
		u = _u;
		v = _v;
		w = _w;
		id = _id;
	}
};

bool operator<(edge a, edge b) {
	return a.w < b.w;
}

struct Edge
{
	int to, w, id;
	Edge() {}
	Edge(int _to, int _w, int _id) {
		to = _to;
		w = _w;
		id = _id;
	}
};


int p[maxn], pid[maxn];

vector< Edge > g[maxn];

vector<int> cycle;


void dfs(int v, int par = -1, int idpar = -1) {
	p[v] = par;
	pid[v] = idpar;
	for (auto go : g[v]) {
		int to = go.to;
		if (to != par) {
			dfs(to, v, go.id);
		}
	}
}


int get_lca(int u, int v) {
	vector<int> a, b;
	while (u != -1) {
		a.push_back(u);
		u = p[u];
	}
	while (v != -1) {
		b.push_back(v);
		v = p[v];
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	int ptr = -1;
	int sz = min((int)a.size(), (int)b.size());
	while (ptr + 1 < sz && a[ptr + 1] == b[ptr + 1]) ++ptr;
	return a[ptr];
}


vector<int> get(int u, int v) {
	int lca = get_lca(u, v);
	vector<int> res;
	while (u != lca) {
		res.push_back(pid[u]);
		u = p[u];
	}
	while (v != lca) {
		res.push_back(pid[v]);
		v = p[v];
	}
	return res;
}


signed main() {
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	vector< bool > used_edge(m + 1);
	vector< edge > e;
	vector<int> we(m + 1);
	forn(it, m) {
		int u, v, w;
		cin >> u >> v >> w;
		e.push_back(edge(u, v, w, it));
		we[it] = w;
	}
	sort(e.begin(), e.end());
	int res1 = 0, res2 = 0;
	DSU dsu = DSU(n);
	vector< edge > mst;
	for (edge ee : e) {
		int u = ee.u, v = ee.v, w = ee.w, id = ee.id;
		if (!dsu.con(u, v)) {
			used_edge[ee.id] = 1;
			dsu.join(u, v);
			g[u].push_back(Edge(v, w, id));
			g[v].push_back(Edge(u, w, id));
			mst.push_back(ee);
			res1 += w;
		}
	}
	dfs(1);
	res2 = INF;
	for (edge ee : e) {
		if (!used_edge[ee.id]) {
			int u = ee.u, v = ee.v, w = ee.w;
			int cur = res1 + w;
			vector<int> kek = get(u, v);
			int maximal = 0;
			for (int keke : kek) uax(maximal, we[keke]);
			cur -= maximal;
			uin(res2, cur);
		}
	}
	if (m < n - 1) res1 = -1;
	if (m <= n - 1) res2 = -1;
	if (res2 == INF) res2 = -1;
	cout << "Cost: " << res1 << "\n";
	cout << "Cost: " << res2 << "\n";
    return 0;
}



// kek