#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;


priority_queue <pair <int, int> >q;
vector <pair<int, int> > g[200005];
vector <pair<int, int> >::iterator it;

int n, m, t[200005], dist[200005], v[200005];

void citire()
{
    scanf("%d %d", &n, &m);
    int x, y, c;
    for(int i=1; i<=m; ++i)
    {
        scanf("%d %d %d", &x, &y, &c);
        g[x].push_back(make_pair(c, y));
        g[y].push_back(make_pair(c, x));
    }
    dist[1]=0;
    t[1]=1;
    v[1]=1;
    for(int i=2; i<=m; ++i)
    {
        t[i]=i;
        dist[i]=1005;
    }
    q.push(make_pair(0, 1));
}

void actualizareDistantaTata(int c, int x, int c1, int x1)
{
    if(dist[x1]>c1)
    {
        dist[x1]=c1;
        t[x1]=x;
        q.push(make_pair(-c1, x1));
    }
}

void rezolvare()
{
    while(!q.empty())
    {
        int c=(-1)*q.top().first, x=q.top().second;
        q.pop();
        v[x]=1;
        for(it=g[x].begin(); it!=g[x].end(); ++it)
        {
            if(v[it->second]==0)
                {
                    actualizareDistantaTata(c, x, it->first, it->second);
                }
        }
    }
}

void afisare()
{
    int distArbore=0;
    for(int i=2; i<=n; ++i)
        distArbore+=dist[i];
    printf("%d\n", distArbore);
    printf("%d\n", n-1);
    for(int i=2; i<=n; ++i)
        printf("%d %d\n", i, t[i]);
}

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