#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int mare = 2e9+7;
void dijkstra(int start);
struct ura
{
    int nod, cost;
    bool operator < (const ura &aux) const
    {
        return cost > aux.cost;
    }
};

priority_queue<ura> q;
int d[200001], ult[200001], n, m, suma;
bool viz[200001];
vector<pair<int, int>> sol, vecini[200001];

int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin>>x>>y>>c;
        vecini[x].push_back({y, c});
        vecini[y].push_back({x, c});
    }
    dijkstra(1);
    fout<<suma<<"\n"<<n-1<<"\n";
    for(auto i : sol)
        fout<<i.first<<" "<<i.second<<"\n";






    return 0;
}

void dijkstra(int start)
{
    for(int i = 1; i <= n; ++i)
        d[i] = mare;
    d[start] = 0;
    q.push({start, 0});

    while(!q.empty())
    {
        int nod = q.top().nod, crtcost = q.top().cost;
        q.pop();
        if(viz[nod])
            continue;
        viz[nod] = 1;
        suma += crtcost;
        if(nod != start)
            sol.push_back({ult[nod], nod});
        for(auto i : vecini[nod])
        {
            if(viz[i.first])
                continue;
            if(d[i.first] > i.second)
            {
                ult[i.first] = nod;
                d[i.first] = i.second;
                q.push({i.first, i.second});
            }
        }
    }
}