problem356

#include <bits/stdc++.h>

using namespace std;

struct Edge
{
    int u, v;
    int w;
    int id;
    bool operator <(Edge x)
    {
        return w < x.w || (w == x.w && id < x.id);
    }
};

bool cmp(Edge a, Edge b)
{
    return a.id < b.id;
}

vector<Edge> g;

vector<int> p;

int get(int v)
{
    if (v == p[v])
        return v;
    return p[v] = get(p[v]);
}

void unite(int a, int b)
{
    a = get(a);
    b = get(b);
    if (a == b)
        return;
    if (rand() % 2)
        p[a] = b;
    else
        p[b] = a;
}


const int INF = -1e9;
int uu = 0;

int dfs(int v, int s, int ep, vector< set<int> > &g1, vector<int> &used, vector<int> &path)
{
    used[v] = uu;
    for (auto ei : g1[v])
    {

        Edge e = g[ei];
        int to = e.v;
        if (to == v)
            to = e.u;
        if (to == s && ei != ep)
        {
            path.push_back(ei);
            return 1;
        }
        if (used[to] != uu)
        {
            int r = dfs(to, s, ei, g1, used, path);
            if (r)
            {
                path.push_back(ei);
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    p.resize(n);
    for (int i = 0; i < n; i++)
        p[i] = i;

    g.resize(m);
    for (int i = 0; i < m; i++)
    {
        cin >> g[i].v >> g[i].u >> g[i].w;
        g[i].v--;
        g[i].u--;
        g[i].id = i;
    }
    sort(g.begin(), g.end());
    vector<int> used(m, 0);
    vector<set<int> > g1(n);
    set<int> mst;
    for (int i = 0; i < m; i++)
    {
        int v = g[i].v;
        int u = g[i].u;
        int v1 = get(v);
        int u1 = get(u);
        if (u1 == v1)
            continue;
        unite(u1, v1);
        used[i] = 1;
        mst.insert(i);
        g1[u].insert(i);
        g1[v].insert(i);
    }
    vector<int> used1(n, 0);
    int q = -1; // delete it
    int p = -1; // add it
    vector<int> path;
    for (int i = 0; i < m; i++)
    {
        if (!used[i])
        {
            int u = g[i].u;
            int v = g[i].v;
            g1[v].insert(i);
            g1[u].insert(i);
            uu++;
            path.clear();
            int d = dfs(u, u, -1, g1, used1, path);
            if (d)
            {
                int tmp = -1;
                for (auto e : path)
                {
                    if (e != i && (tmp == -1 || g[e].w > g[tmp].w))
                        tmp = e;
                }
                if (p == -1 || q == -1 || (tmp != -1 && g[i].w - g[tmp].w < g[p].w - g[q].w))
                {
                    p = i;
                    q = tmp;
                }
            }
            g1[v].erase(i);
            g1[u].erase(i);

        }
    }
    if (q == -1)
    {
        cout << -1;
        return 0;
    }
    mst.erase(q);
    mst.insert(p);
    long long wei = 0;
    vector<Edge> res;
    for (auto x : mst)
    {
        res.push_back(g[x]);
        wei += (long long)g[x].w;
    }
    sort(res.begin(), res.end(), cmp);
    if ((int)res.size() != n - 1)
    {
        cout << -1;
        return 0;
    }

    cout << wei << endl;

    for (auto x : res)
        cout << x.v + 1 << " " << x.u + 1 << " " << x.w << endl;
    return 0;
}