///not finished :(

#include <cstdio>
#include <vector>
#include <tuple>
#include <queue>

#define INF 2000000000
#define NMAX 200000
using namespace std;
FILE *in=fopen("apm.in", "r"), *out=fopen("apm.out", "w");
int n, m;
int us[NMAX+2], af[NMAX+2], x, y, c;
vector<pair<int, int>> vp[NMAX+2];
int prim(int x)
{
    priority_queue<tuple<int, int, int>> qul; //cost, node, lastnode
    us[x]=0; //x node used
    int totcost=0; //total returned cost
    for(int i=0; i<vp[x].size(); i++)
    {
        qul.push({vp[x][i].second, vp[x][i].first, x});
    }
    //qul.push({mincost, newnode, x});
    while(!qul.empty())
    {
        tuple<int, int, int> tp=qul.top();
        qul.pop();
        int curnode=get<1>(tp);
        int lastnode=get<2>(tp);
        int curcost=get<0>(tp);
        if(us[curnode]>curcost)
        {
            totcost-=us[curnode];
            totcost+=curcost;
            us[curnode]=curcost;
            af[curnode]=lastnode;

            for(int i=0; i<vp[curnode].size(); i++)
            {
                qul.push({vp[curnode][i].second, vp[curnode][i].first, curnode});
            }
        }
    }

    return totcost;
}


int main()
{
    fscanf(in, "%d %d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        fscanf(in, "%d %d %d", &x, &y, &c);
        vp[x].push_back({y, c});
        vp[y].push_back({x, c});
    }

    fprintf(out, "%d\n%d\n", prim(1), n-1);
    for(int i=2; i<=n; i++)
    {
        fprintf(out, "%d %d\n", i, af[i]);
    }
    return 0;
}