#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n, m, i, parent[105], sz[105], viz[105];
vector < pair < int, int >> ans;
struct edge{
    int a, b, c;
};
bool cmp(edge x, edge y) {
    return x.c < y.c;
}
edge v[10005];

int findparent(int node) {
    if(node == parent[node])
        return node;
    return parent[node] = findparent(parent[node]);
}

void unire(int n1, int n2) {
    if(sz[n1] < sz[n2])
        swap(n1, n2);
    parent[n2] = n1;
    sz[n1] += sz[n2];
}

int main() {
    ios_base::sync_with_stdio(false);
    in.tie(NULL);
    in >> n >> m;
    for(i = 1; i <= m; ++i)
        in >> v[i].a >> v[i].b >> v[i].c;
    sort(v + 1, v + m + 1, cmp);
    for(i = 1; i <= n; ++i) {
        parent[i] = i;
        sz[i] = 1;
    }
    int sum = 0;
    for(i = 1; i <= m; ++i) {
        int n1, n2, cost;
        n1 = findparent(v[i].a);
        n2 = findparent(v[i].b);
        cost = v[i].c;
        if(n1 == n2)
            continue;
        ans.push_back({v[i].a,v[i].b});
        sum += cost;
        unire(n1, n2);
    }
    if(ans.size() != n-1) out << -1;
    else {
        out << sum << '\n' << n -1 << '\n';
        for(auto x : ans)
            out << x.first << ' ' << x.second << '\n';
    }

    return 0;
}