#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,p,m,x,y,c;
const int inf=1000000000;
vector <pair<int,int> > v[200010],sol;
priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > srt;
long long total;
int viz[200010],d[200010];
int tt[200010];
int main()
{   f>>n>>m;
    while(f>>x>>y>>c)
    {   v[x].push_back({c,y});
        v[y].push_back({c,x});
    }
    p=1;
    for(int i=1;i<=n;i++) d[i]=inf;
    d[p]=0;
    srt.push(make_pair(0,p));
    while(!srt.empty())
    {   pair<int,int> t=srt.top();
        srt.pop();
        int cost=t.first;
        int nod=t.second;
        if(!viz[nod])
        {   viz[nod]=1;
            vector<pair<int,int> > :: iterator it=v[nod].begin(),sf=v[nod].end();
            for(;it!=sf;it++)
                if(d[it->second]>it->first and !viz[it->second])
            {   d[it->second]=it->first;
                srt.push({d[it->second],it->second});
                tt[it->second]=nod;
            }
        }
    }
    for(int i=1;i<=n;i++)
        total+=d[i];
    g<<total<<'\n';
    g<<n-1<<'\n';
    for(int i=1;i<=n;i++)
        if(tt[i]!=0) g<<tt[i]<<' '<<i<<'\n';
    return 0;
}