#include <cstdio>
#include <queue>
#include <utility>
#include <vector>
#include <cstring>
using namespace std;

priority_queue < int, vector< pair < pair <int, int> , int > >, greater < pair < pair <int, int> , int > > > Q;
vector < pair <int, int> > sol[200005];

int n,m;
int comp[200005];
int vfstart;
void debug()
{   pair < pair <int, int> , int > x;
    while(!Q.empty())
    {
        x = Q.top ();
        printf("%d %d %d\n",x.second,x.first.second,x.first.first);
        Q.pop();
    }
}
void citire()
{
    scanf("%d %d",&n,&m);
    for(int i = 0 ;i < m; i++)
        {
            pair < pair <int, int> , int > x;

            scanf("%d %d %d",&x.second,&x.first.second,&x.first.first);

            Q.push(x);
        }

    //debug();

    for(int i=1;i<=n;i++)
    comp [i] = i;

}
int viz[200005];

void comp_NR(int c, int x)
{

    comp[x] = c;
    viz[x] = 1;
    for(int i=0;i<sol[x].size();i++)
        {   if(!viz[ sol[x][i].second ])
            comp_NR (c , sol[x][i].second);
        }

}
int cost;
void solve()
{
    pair < pair <int, int> , int > x = Q.top();
    vfstart = x.first.second;
    int nr=0;
    while (nr < n - 1)
    {
       x = Q.top();
            if( comp[x.second] != comp[x.first.second] )
            {
                comp_NR(comp[x.second],x.first.second);
                 memset(viz,0,sizeof(viz));
                sol[x.second].push_back(x.first);
                int aux = x.first.second;
                x.first.second = x.second;
                x.second = aux;
                sol [x.second].push_back(x.first);
                nr++;
                cost += x.first.first;
            }
            Q.pop();
    }

}

int vizafis[200005];

void dfs(int start)
{

    vizafis[start] = 1;

    for(int i=0;i<sol[start].size();i++)
        {   if(!vizafis[ sol[start][i].second ])
            {   printf("%d %d\n",start,sol[start][i].second);
                dfs (sol[start][i].second);
            }
        }
}

void afisare()
{
    printf("%d\n%d\n",cost,n-1);
    int k=1;
    dfs(vfstart);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    solve();
    afisare();
    return 0;
}