#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef struct qwer{int x,y,pr;}B;
B E[1000000];
int sec,fir,goal;
bool used[1000000];
bool ar[501];
int jl[501],n;
int dis[501][501];
bool cmp(B a,B b)
{
return a.pr<b.pr;
}
int map[501][501];
int jg[501][501];
int ft[502];
int ance[501][501];
int find(int x)
{
if (x==ft[x])return x;
return ft[x]=find(ft[x]);
}
void check(int now,int ft,int l)
{
int i;
for (i=1;i<=jl[0];i++)
{
if (now==jl[i])continue;
if (l>dis[ft][jl[i]])
dis[now][jl[i]]=dis[jl[i]][now]=l;
else
dis[now][jl[i]]=dis[jl[i]][now]=dis[ft][jl[i]];
}
jl[0]++;jl[jl[0]]=now;
for (i=1;i<=map[now][0];i++)
{
if (map[now][i]==ft)continue;
check(map[now][i],now,jg[now][i]);
}
jl[0]--;
}
void LCA(int now,int b)
{
int i;ar[now]=1;
for (i=1;i<=map[now][0];i++)
{
if (map[now][i]==b)continue;
LCA(map[now][i],now);
ft[find(map[now][i])]=now;
}
for (i=1;i<=n;i++)
if (ar[i]&&i!=now)
{
ance[now][i]=ance[now][i]=find(i);
}
}
int main()
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
int i,j,k,l,m;
scanf("%d %d\n",&n,&m);
memset(used,0,sizeof(used));
for (i=1;i<=m;i++)
scanf("%d %d %d\n",&E[i].x,&E[i].y,&E[i].pr);
sort(E+1,E+1+m,cmp);
int fini=0;
int ans1=0,ans2=0;
memset(map,0,sizeof(map));
for (i=1;i<=n;i++)ft[i]=i;
for (i=1;i<=m;i++)
{
int x=find(E[i].x),y=find(E[i].y);
if (x!=y)
{
fini++;
used[i]=1;
ans1+=E[i].pr;
map[E[i].x][++map[E[i].x][0]]=E[i].y;
jg[E[i].x][map[E[i].x][0]]=E[i].pr;
map[E[i].y][++map[E[i].y][0]]=E[i].x;
jg[E[i].y][map[E[i].y][0]]=E[i].pr;
ft[y]=x;
if (fini==n-1)break;
}
}
if (fini<n-1){printf("Cost: -1\nCost: -1\n");return 0;}
if (m==n-1){printf("Cost: %d\nCost: -1\n",ans1);return 0;}
ans2=~0u>>1;
memset(jl,0,sizeof(jl));
jl[0]=0;
memset(dis,-1,sizeof(dis));
check(1,0,-1);
memset(ar,0,sizeof(ar));
for (i=1;i<=n;i++)ft[i]=i;
LCA(1,-1);
for (i=1;i<=m;i++)
{
if (used[i])continue;
int wh=ance[E[i].x][E[i].y];
int bone=max(dis[wh][E[i].x],dis[wh][E[i].y]);
if (ans1-bone+E[i].pr<ans2)
ans2=ans1-bone+E[i].pr;
}
printf("Cost: %d\nCost: %d\n",ans1,ans2);
return 0;
}
