#include <bits/stdc++.h>

using namespace std;
int stramos[200005], sz[200005];
int find_parent(int a)
{
    if(stramos[a]==a)
        return a;
    return stramos[a]=find_parent(stramos[a]);
}
void unite(int a, int b)
{
    a=find_parent(a);
    b=find_parent(b);
    if(sz[a]>sz[b])
        swap(a,b);
    stramos[a]=b;
    sz[b]+=sz[a];
}
vector<pair<int,int>>graph[200005];
bool viz[200005];
int main()
{
    ///algoritmul lui Prim
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a,b,d;
        cin>>a>>b>>d;
        graph[a].push_back({b,d});
        graph[b].push_back({a,d});
    }
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
    viz[1]=1;
    for(auto x: graph[1])
        pq.push({x.second, 1, x.first});
    vector<pair<int,int>>muchii_pastrate;
    int rasp=0;
    for(int i=1; i<n; i++)
    {
        while(!pq.empty())
        {
            auto [cost, a, b]=pq.top();
            if(viz[b])
            {
                pq.pop();
                continue;
            }
            break;
        }
        if(pq.empty())
        {
            cout<<-1<<'\n'; ///nu putem face un arbore
            return 0;
        }
        auto [cost,a,b]=pq.top();
        rasp+=cost;
        pq.pop();
        viz[b]=1;
        muchii_pastrate.push_back({a,b});
        for(auto x: graph[b])
            pq.push({x.second, b, x.first});
    }
    cout<<rasp<<'\n'<<n-1<<'\n';
    for(auto x: muchii_pastrate)
        cout<<x.first<<" "<<x.second<<'\n';
    return 0;
}