#include <bits/stdc++.h>
#define pii pair <int, int>
#define Nmax 200002
#define f first
#define s second
#define pb(x) push_back(x)
#define INF 2000000000
FILE *fin  = freopen("apm.in", "r", stdin);
FILE *fout = freopen("apm.out", "w", stdout);

using namespace std;
int N, M, parent[Nmax], sol, key[Nmax];
vector <pii> G[Nmax];
struct comp
{
    bool operator() (const pii &a, const pii &b)
    {
        return a.s > b.s;
    }
};
priority_queue< pii, vector< pii >, comp > Q;
bitset <Nmax> mst;
void read()
{
    int x, y, c;
    scanf("%d %d", &N, &M);
    while(M --)
    {
        scanf("%d %d %d", &x, &y, &c);
        G[x].pb(pii(y, c));
        G[y].pb(pii(x, c));
    }
}
void solve()
{
    int i, u, v, w;
    for(i = 2; i <= N; ++ i)
        key[i] = INF;
    parent[1] = -1;
    Q.push(pii(1, 0));

    while(!Q.empty())
    {
        /// Pick thd minimum key vertex from the set of vertices
        /// not yet included in MST
        u = Q.top().f;
        if(mst.test(u)) {Q.pop();continue;}
        sol += Q.top().s;
        Q.pop();

        /// Add the picked vertex to the MST Set
        mst.set(u);

        /// Update key value and parent index of the adjacent vertices of
        /// the picked vertex. Consider only those vertices which are not yet
        /// included in MST
        int sz = G[u].size();
        for(int it = 0; it < sz; ++ it)
        {
            v = G[u][it].f;
            w = G[u][it].s;
            if(mst.test(v) == 0 && key[v] >  w)
            {
                parent[v] = u;
                key[v] =  w;
                Q.push(pii(v, key[v]));
            }
        }
    }
}
void write()
{
    int edge = N - 1;
    printf("%d\n%d\n", sol, edge);
    for(int i = 2; i <= N; ++ i)
        printf("%d %d\n", parent[i], i);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}