#include<fstream>
#include<vector>
#include<queue>
#include<string.h>
#include<iostream>
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int d[200005],tata[200005],viz[200005],n,m,suma,x,y,c,i;
vector< pair<int, int> > v[200005];
priority_queue< pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q;
void dijkstra(int nod)
{
    memset(d,inf,sizeof(d));
    Q.push(make_pair(0,nod));
    d[nod]=0;
    while(!Q.empty())
    {
        int j=Q.top().second;
        int cost=Q.top().first;
        Q.pop();
        if(viz[j]==1)
            continue;
        viz[j]=1;
        for(i=0;i<v[j].size();i++)
            if(d[v[j][i].first]>v[j][i].second && viz[v[j][i].first]==0)
            {
                d[v[j][i].first]=v[j][i].second;
                tata[v[j][i].first]=j;
                Q.push(make_pair(d[v[j][i].first],v[j][i].first));
            }
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }
    /*for(i=1;i<=n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            cout<<i<<" "<<j<<" "<<v[i][j].first<<" "<<v[i][j].second<<"\n";
        }
    }*/
    dijkstra(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]==inf)
            d[i]=0;
        //cout<<tata[i]<<" "<<i<<" "<<d[i]<<"\n";
        suma=suma+d[i];
    }
    fout<<suma<<"\n"<<n-1<<"\n";
    for(i=2;i<=n;i++)
    {
        if(d[i]==inf)
            d[i]=0;
        fout<<tata[i]<<" "<<i<<"\n";
        
    }
    fin.close();
    fout.close();
    return 0;
}
/*
 9 14
 1 2 10
 1 3 -11
 2 4 11
 2 5 11
 5 6 13
 3 4 10
 4 6 12
 4 7 5
 3 7 4
 3 8 5
 8 7 5
 8 9 4
 9 7 3
 6 7 11
 */