#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define nmax 200001
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,apm,x,y,c,t[nmax],cost[nmax];
bool viz[nmax];
struct muchie{
    int x,c;
};
vector<muchie>v[nmax];
struct cmp{
    bool operator()(const muchie& a,const muchie& b){
        return a.c>b.c;
    }
};
priority_queue<muchie,vector<muchie>,cmp>h;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }
    for(int i=2;i<=n;i++)
        cost[i]=INT_MAX;
    h.push({1,0});
    while(!h.empty()){
        int nod=h.top().x,c=h.top().c;
        h.pop();
        if(viz[nod])
            continue;
        viz[nod]=1;
        apm+=c;
        for(auto i:v[nod])
            if(!viz[i.x]&&cost[i.x]>i.c){
                cost[i.x]=i.c;
                t[i.x]=nod;
                h.push({i.x,i.c});
            }
    }
    cout<<apm<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++)
        cout<<i<<" "<<t[i]<<'\n';
    return 0;
}