#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 7;
const int MAXN = 507;
const int MAXM = MAXN * MAXN;

struct Edge {
  	int u, v, c;
};

int n, m;
Edge e[MAXM];

bool comp(Edge a, Edge b) {
 	return a.c < b.c;
}

int cnt[MAXN], par[MAXN];

int root(int u) {
	if (par[u] == u) return u;
	else return par[u] = root(par[u]);
}

bool merge(int u, int v) {
	u = root(u);
	v = root(v);
 	if (u == v) return 0;

 	if (cnt[u] < cnt[v]) {
 	 	cnt[v] += cnt[u];
 	 	par[u] = v;
 	}
 	else {
 		cnt[u] += cnt[v];
 		par[v] = u;
 	}

 	return 1;
}

bool in_mst[MAXM];
int get(int del) {
	for (int i = 0; i < n; ++i) {
		par[i] = i;
		cnt[i] = 1;
	}

    int c = 0;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
    	if (del == i) continue;
    	if (merge(e[i].u, e[i].v)) {
    	 	++c;
    	 	ans += e[i].c;
    	 	if (del == -1) in_mst[i] = 1;
     	}
    }

    if (c != n - 1) return INF;
    else return ans;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
	 	cin >> e[i].u >> e[i].v >> e[i].c;
	 	--e[i].u; --e[i].v;
	}
	sort(e, e + m, comp);

	cout << "Cost: ";
	int ans1 = get(-1);
	if (ans1 == INF) cout << "-1\n";
	else cout << ans1 << '\n';

	int ans2 = INF;
	for (int i = 0; i < m; ++i) {
	 	if (in_mst[i]) {
	 	 	ans2 = min(ans2, get(i));
	 	}
	}

	cout << "Cost: ";
	if (ans2 == INF) cout << "-1\n";
	else cout << ans2 << '\n';

	return 0;
}