#include <iostream>
#include <fstream>
#include <tuple>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1000000000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,x,y,z,d[200001],t[200001],costmin,viz[200001],counter,s;
vector <vector <int>> v(200001);
vector <vector <int>> cost(200001);
auto cmp=[](tuple <int,int,int> a,tuple <int,int,int> b)
{
    int a1,a2,acost,b1,b2,bcost;
    tie (a1,a2,acost)=a;
    tie (b1,b2,bcost)=b;
    if (acost>bcost)
        return 1;
    else return 0;
};
priority_queue <tuple <int,int,int> , vector <tuple<int,int,int>> , decltype(cmp)> q(cmp);
/*int dad (int cur)
{
    if (t[cur]==cur)
        return cur;
    else return t[cur]=dad(t[cur]);
}*/
int main()
{
    f>>n>>m;
    for (int i=1; i<=n; i++)
    {
        d[i]=INF;
        t[i]=i;
    }
    for (int i=1; i<=m; i++)
    {
        f>>x>>y>>z;
        v[x].push_back(y);
        v[y].push_back(x);
        cost[x].push_back(z);
        cost[y].push_back(z);
        //v.push_back(make_tuple (x,y,z));
    }
    q.push(make_tuple(1,0,0));
    d[1]=0;
    //viz[1]=1;
    while (!q.empty())
    {
        int cur,previous,pc;
        tie (cur,previous,pc)=q.top();
        viz[cur]=1;
        q.pop();
        for (int i=0; i<v[cur].size(); i++)
        {
            int next=v[cur][i],price=cost[cur][i];
            if (viz[next]==0 && d[next]>price)
            {
                d[next]=price;
                t[next]=cur;
                //viz[next]=1;
                q.push(make_tuple(next,cur,price));
            }
        }
    }
    for (int i=1; i<=n; i++)
    {
        s+=d[i];
        if (t[i]!=i)
        counter++;
    }
  //  sort(v.begin(),v.end(),cmp);
    g<<s<<'\n'<<counter<<'\n';
    for (int i=1; i<=n; i++)
    {
        if (t[i]!=i)
        {
            g<<i<<' '<<t[i]<<'\n';
        }
    }
    return 0;
}