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

#define edge pair<int,int>
#define DIM 200001

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

int N, M, x, y, z, minCost;
int C[DIM];
bool Vis[DIM];
vector <edge> Graph[DIM];
vector <edge> Edge;
priority_queue <edge, vector<edge> , greater<edge> > P;

void Input();
void APM();
void Output();

int main()
{
    Input();
    APM();
    Output();

    is.close();
    os.close();
    return 0;
}

void Input()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y >> z;
        Graph[x].push_back(make_pair(x,z));
        Graph[y].push_back(make_pair(y,z));
        Edge.push_back(make_pair(x,y));
    }
    for ( int i = 2; i <= N; ++i )
        C[i] = 0x3f3f3f3f;
}

void APM()
{
    P.push(make_pair(1,0));
    Vis[1] = 1;
    int node, t;
    while ( !P.empty() )
    {
        node = P.top().first;
        for (const auto& v : Graph[node])
            if ( !Vis[v.first] && C[v.first] > v.second )
            {
                C[v.first] = v.second;
                t = v.first;
                P.push(make_pair(v.first,v.second));
            }

        minCost += C[node];
        Edge.push_back(make_pair(t,node));
        while ( !P.empty() && Vis[P.top().first]);
            P.pop();
        Vis[node] = 1;
    }
}

void Output()
{
    os << minCost << " " << Edge.size() << '\n';
    for (const auto& node : Edge)
        os << node.first << " " << node.second << '\n';
}