#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

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

#define cin fin
#define cout fout

const int NMAX=2e5+5;

struct elem{
    int x;
    int y;
    int c;

    bool operator<(const elem  &other) const
    {
        return c>other.c;
    }
};

vector<pair<int,int>>v[NMAX];
pair<int,int>ans[NMAX];

bool viz[NMAX];
int n;

void prim(int p)
{
    int kon=0,s=0;
    priority_queue<elem>pq;
    viz[p]=true;
    for(auto i:v[p])
        pq.push({p,i.first,i.second});
    while(!pq.empty())
    {
        elem p=pq.top();
        pq.pop();
        if(kon==n-1)
            break;
        if(!viz[p.y])
        {
            s+=p.c;
            viz[p.y]=true;
            ans[++kon]={p.x,p.y};
            for(auto i:v[p.y])
                if(!viz[i.first])
                    pq.push({p.y,i.first,i.second});
        }
    }
    cout<<s<<"\n";
    cout<<kon<<"\n";
    for(int i=1;i<=kon;i++)
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int i,j,m,s=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    prim(1);
    return 0;
}