#include <iostream> //Prim
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#include <list>
using namespace std;
//distanta la cel mai apropiat vecin de s, tata, vf vizitate
vector<int> d;
vector<int> t;
vector<int> viz;

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

typedef pair<int, int> pi;

int main ()
{
    int n, m, s, i, j, x, y, c, sum = 0;
    vector<vector< pair<int, int>>> Graf; //liste de adiacenta
    fin>>n>>m;
    Graf.resize(n + 1);
    d.resize(n + 1, 1001);
    t.resize(n + 1, 0);
    viz.resize(n + 1, 0);
    for(i=0; i<m; i++)
    {
        fin>>x>>y>>c;
        Graf[x].push_back({y, c});
        Graf[y].push_back({x, c});
    }
    s = 1; d[s]=0;

    priority_queue< pi, vector<pi>, greater<pi>> Q;
    Q.push({d[s], s});
    while(!Q.empty())
    {
        x=Q.top().second; //nod
        Q.pop(); viz[x]++;
        for(auto i: Graf[x]) //vecinii lui x
        {
            y=i.first;
            j=i.second;
            if(viz[y]==0 && d[y]>j)
            {
                if(d[y] != 1001){
                    sum = sum - d[y] + j;
                }else sum += j;
                t[y]=x;
                d[y]=j;
                Q.push({d[y], y});
            }
        }
    }
    fout << sum << endl << n - 1 << endl;
    for(i=1; i<=n; i++)
        if(t[i]!=0) fout<<t[i]<<" "<<i<<endl;

    return 0;
}