#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

const int N=200000;
const int M=400000;
const int INF=1e9;

struct muchie
{
    int x, y, c;
};

std::vector<int> v[N+1];
muchie edge[M+1];

/// daca se afla sau nu in graful curent
bool ingraph[N+1];

struct elem
{
    int first;
    int second;
    int fromium;
};

bool compare(elem a, elem b)
{
    return a.first>b.first;
}

std::priority_queue<elem, std::vector<elem>, decltype(&compare)> q(&compare);

int main()
{
    int n, m;

    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>edge[i].x>>edge[i].y>>edge[i].c;
        v[edge[i].x].push_back(i);
        v[edge[i].y].push_back(i);
    }

    int sum=0;
    std::vector<std::pair<int, int>> ans;

    q.push({0, 1, 1});
    while(!q.empty())
    {
        int curr=q.top().second;
        int dist_curr=q.top().first;
        int fromium=q.top().fromium;
        q.pop();

        if(!ingraph[curr])
        {
            ans.push_back({fromium, curr});

            ingraph[curr]=1;
            sum+=dist_curr;

            for(int i : v[curr])
            {
                int to=edge[i].x+edge[i].y-curr;
                int cost=edge[i].c;

                if(!ingraph[to])
                {
                    q.push({cost, to, curr});
                }
            }
        }
    }

    out<<sum<<"\n"<<n-1<<"\n";
    for(int i=ans.size()-1; i>=1; i--)
    {
        out<<ans[i].first<<" "<<ans[i].second<<"\n";
    }
}