#include <fstream>
#include <queue>
#include <bitset>
using namespace std;

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

const int NMAX = 1e3 + 1;
const int INF = 1e6;
int d[NMAX],n,m,pred[NMAX],cost;

vector <pair<int,int>> M[NMAX];
priority_queue<pair<int,int>> pq;
bitset <NMAX> folosit;

void prim()
{
    for(int i = 2; i <= n; i++)
    {
        d[i] = INF;
    }
    pq.push({0,1});
    while(!pq.empty())
    {
        int x = pq.top().second;
        pq.pop();
        if(folosit[x])
        {
            continue;
        }
        cost += d[x];
        folosit[x] = true;
        for(auto p : M[x])
        {
            int y = p.first;
            int c = p.second;
            if(!folosit[y] && c < d[y])
            {
                d[y] = c;
                pred[y] = x;
                pq.push({-c,y});
            }
        }
    }
}

int main(int argc, const char * argv[])
{
    in >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        M[x].push_back({y,c});
        M[y].push_back({x,c});
    }
    prim();
    out << cost << " " << n-1 << "\n";
    for(int i = 2;i <= n; i++)
    {
        out << i << " " << pred[i] << "\n";
    }
    in.close();
    return 0;
}