#include <bits/stdc++.h>
#define lim 400005
#define oo 10000000000
using namespace std;

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

int n, m, lung[lim/2], result[lim/2], parcurs[lim/2], pp[lim/2], lungime=0;

struct cmp
{
    bool operator()(int a, int b)
    {
        return lung[a]>lung[b];
    }
};
vector < pair<int, int>> v[lim];
priority_queue<int, vector <int>, cmp> q;

void read()
{

    int x, y, c;
    in>>n>>m;
    lung[1]=0;
    for(int i=2; i<=n; ++i)
    {
        lung[i]=oo;
    }
    for(int i=1; i<=m; ++i)
    {
        in>>x>>y>>c;
        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }
}

void solve(int nr)
{
    q.push(nr);
    while(!q.empty())
    {
        nr=q.top();
        q.pop();
        for(int i=0; i<v[nr].size(); ++i)
        {
           /// cout<<v[nr][i].first<<" "<<v[nr][i].second<<'\n';
            if(lung[v[nr][i].first]>v[nr][i].second && pp[v[nr][i].first]==0)
            {
                lung[v[nr][i].first]=v[nr][i].second;
                result[v[nr][i].first]=nr;
                if(parcurs[v[nr][i].first]==0)
                {
                    q.push(v[nr][i].first);
                    parcurs[v[nr][i].first]=1;
                }
            }
        }
        lungime+=lung[nr];
        pp[nr]=1;
        parcurs[nr]=0;
    }

}

void print()
{
    out<<lungime<<'\n'<<n-1<<'\n';
    for(int i=2; i<=n; ++i)
    {
        out<<i<<" "<<result[i]<<'\n';
    }
}

int main()
{
    read();
    solve(1);
    print();
    return 0;
}