#include <bits/stdc++.h>
using namespace std;
 
#define BRANCO 0
#define CINZA 1
#define PRETO 2
 
typedef pair<int, pair<int, int> > ip;
 
vector<ip> MST;
vector<ip> arestas;
vector<ip> outMST;
vector<int> graph[502];
int pai[502], peso[502], cor[502], firstRead, cost1, cost2 = -1;
int v, e, x, y, w;
bool trouve;
 
void dfs(int vertice)
{
    cor[vertice] = CINZA;
 
    for (int i = 0; i < graph[vertice].size(); i++) {
        if (cor[graph[vertice][i]] == BRANCO)
            dfs(graph[vertice][i]);
    }
}
 
bool DFS()
{
    for (int i = 1; i <= v; i++) {
        if (cor[i] == BRANCO) {
            if (i > 1)
                return false;
            dfs(i);
        }
    }
    return true;
}
 
int FIND_SET(int v)
{
    if (pai[v] != v)
        pai[v] = FIND_SET(pai[v]);
    return pai[v];
}
 
void UNION(int v, int u)
{
    v = FIND_SET(v);
    u = FIND_SET(u);
 
    if (u == v)
        return;
    if (peso[u] > peso[v])
        pai[v] = u;
    else if (peso[v] > peso[u])
        pai[u] = v;
    else {
        pai[v] = u;
        peso[u]++;
    }
}
 
int main()
{
    scanf("%d%d", &v, &e);
 
    for (int i = 1; i <= v; i++) {
        pai[i] = i;
        cor[i] = BRANCO;
    }
 
    ip aresta;
    for (int i = 1; i <= e; i++) {
        scanf("%d%d%d", &x, &y, &w);
        aresta = make_pair(w, make_pair(x, y));
        arestas.push_back(aresta);
    }
 
    stable_sort(arestas.begin(), arestas.end());
 
    int v1, v2;
    for (int i = 0; i < arestas.size(); i++) {
        v1 = arestas[i].second.first;
        v2 = arestas[i].second.second;
        if (FIND_SET(v1) != FIND_SET(v2)) {
            MST.push_back(arestas[i]);
            UNION(v1, v2);
        }
        else
            outMST.push_back(arestas[i]);
    }
 
    for (int i = 0; i < MST.size(); i++) {
        cost1 += MST[i].first;
        graph[MST[i].second.first].push_back(MST[i].second.second);
        graph[MST[i].second.second].push_back(MST[i].second.first);
    }
 
    for (int i = MST.size() - 1; i >= 0; i--) {
 
        for (int j = 0; j < graph[MST[i].second.first].size(); j++) {
            if (graph[MST[i].second.first][j] == MST[i].second.second) {
                graph[MST[i].second.first].erase(graph[MST[i].second.first].begin() + j);
                break;
            }
        }
 
        for (int j = 0; j < graph[MST[i].second.second].size(); j++) {
            if (graph[MST[i].second.second][j] == MST[i].second.first) {
                graph[MST[i].second.second].erase(graph[MST[i].second.second].begin() + j);
                break;
            }
        }
 
        int ind = lower_bound(outMST.begin(), outMST.end(), MST[i]) - outMST.begin();
 
        for (int j = ind; j < outMST.size(); j++) {
            graph[outMST[j].second.first].push_back(outMST[j].second.second);
            graph[outMST[j].second.second].push_back(outMST[j].second.first);
            if (DFS()) {
                cost2 = cost1 + outMST[j].first - MST[i].first;
                trouve = true;
                goto fin;
            }
            else {
                for (int z = 1; z <= v; z++)
                    cor[z] = BRANCO;
                graph[outMST[j].second.first].pop_back();
                graph[outMST[j].second.second].pop_back();
            }
        }
 
        graph[MST[i].second.first].push_back(MST[i].second.second);
        graph[MST[i].second.second].push_back(MST[i].second.first);
    }
 
fin:
 
    if (!trouve) {
        for (int j = 0; j < outMST.size(); j++) {
            graph[outMST[j].second.first].push_back(outMST[j].second.second);
            graph[outMST[j].second.second].push_back(outMST[j].second.first);
            if (DFS())
                cost2 = cost1 + outMST[j].first;
            else {
                for (int z = 1; z <= v; z++)
                    cor[z] = BRANCO;
                graph[outMST[j].second.first].pop_back();
                graph[outMST[j].second.second].pop_back();
            }
        }
    }
 
    printf("Cost: %d\n", cost1);
    printf("Cost: %d\n", cost2);
    return 0;
}