#include <iostream>
#include <algorithm>
#include <vector>
#define ULL unsigned long long

using namespace std;

typedef struct
{
    int a,b;
    ULL d;
}edge;

edge g[250000];
int n,m;
int fa[501];
vector<int> vi;
int check;

bool comp(edge a,edge b)
{
    return a.d<b.d;
}

int fi(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    else
    {
        return fa[x]=fi(fa[x]);
    }
}

int MST(bool &nop)
{
    int i,j,a,b,d,aa,bb;
    ULL ans=0;
    for(i=0;i<=n;i++)
    {
        fa[i]=i;
    }
    for(i=0,j=0;i<n-1;i++)
    {
        for(;j<m;j++)
        {
            if(j==check)
            {
                continue;
            }
            a=g[j].a;
            b=g[j].b;
            d=g[j].d;
            aa=fi(a);
            bb=fi(b);
            if(aa!=bb)
            {
                ans+=d;
                fa[bb]=aa;
                if(check==m)
                {
                    vi.push_back(j);
                }
                break;
            }
        }
    }
    if(j==m)
    {
        nop=true;
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    int i;
    ULL ans=0,hax;
    for(i=0;i<m;i++)
    {
        cin>>g[i].a>>g[i].b>>g[i].d;
    }
    sort(g,g+m,comp);
    check=m;
    bool nop;
    nop=false;
    ans=MST(nop);
    if(nop)
    {
        cout<<"Cost: "<<-1<<endl;
        cout<<"Cost: "<<-1<<endl;
        return 0;
    }
    else
    {
        cout<<"Cost: "<<ans<<endl;
    }
    ans=1e18;
    for(i=vi.size()-1;i>=0;i--)
    {
        check=vi[i];
        nop=false;
        hax=MST(nop);
        if(!nop)
        {
            ans=min(ans,hax);
        }
    }
    if(ans<1e18)
    {
        cout<<"Cost: "<<ans<<endl;
    }
    else
    {
        cout<<"Cost: "<<-1<<endl;
    }
    return 0;
}