#include<cstdio>
#include<algorithm>
const int MAXN=500+5;
const int MAXM=250000+5;
struct Edge{int u,v,w;bool disabled;};
int n,m,father[MAXN],totsel,sel[MAXM];Edge edge[MAXM];
bool comp(Edge a,Edge b){return a.w<b.w;}
int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
int Kruskal(int flag)
{
	int ans=0;
	for(int i=1;i<=n;i++)
		father[i]=i;
	int l=1;
	for(int i=1;i<=m;i++)
	{
		if(edge[i].disabled) continue;
		int fx=find(edge[i].u),fy=find(edge[i].v);
		if(fx!=fy)
		{
			if(flag) sel[++totsel]=i;
			father[fx]=fy;
			ans+=edge[i].w;
			l++;
		}
		if(l==n) return ans;
	}
	return 2147483647;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);
	std::sort(edge+1,edge+m+1,comp);
	int ans=Kruskal(1);
	if(ans==2147483647)
	{
		printf("Cost: -1\nCost: -1");
		return 0;
	}
	printf("Cost: %d\n",ans);
	ans=2147483647;
	for(int i=1;i<=totsel;i++)
	{
		edge[sel[i]].disabled=1;
		ans=std::min(ans,Kruskal(0));
		edge[sel[i]].disabled=0;
	}
	printf("Cost: %d",ans==2147483647?-1:ans);
	return 0;
}