#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

#define MAX 200005

vector < pair < int , int > >v[MAX];
vector < pair < int , int > > :: iterator it;
priority_queue < pair < int , int > > pq;
int viz[MAX],b[MAX],x[MAX],n,m,s,h;

void apm()
{
    pq.push(make_pair(0,1));
    while(!pq.empty())
    {
        int nod=pq.top().second;
        int cost=pq.top().first;
        pq.pop();
        if(viz[nod])
            continue;
        bool ok=1;
        viz[nod]=1;
        s-=cost;
        for(it=v[nod].begin();it!=v[nod].end();it++)
        {
            int anod=it->first;
            int c=it->second;
            if(!viz[anod])
                pq.push(make_pair(-c,anod));
            else if(ok && c==-cost)
            {
                ok=0;
                b[++h]=anod;
                x[h]=nod;
            }
        }
    }
    fout<<s<<"\n"<<h<<"\n";
    for(int i=1;i<=h;i++)
        fout<<b[i]<<" "<<x[i]<<"\n";
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    apm();
    fin.close();
    fout.close();
    return 0;
}