#include <cstdio>
#include <vector>
#include <queue>
#define N_MAX 200001
#define M_MAX 400001
#define pb push_back
#define p push
using namespace std;
FILE *f = freopen("apm.in", "r", stdin);
FILE *g = freopen("apm.out", "w", stdout);
int n, m;
class Vecin {
public:
    int capat, cost;
    Vecin(int capat, int cost)
    {
        this -> capat = capat;
        this -> cost = cost;
    }
};
class muchie{
public:
    int a,  b,  cost;
    muchie(int a, int b, int cost)
    {
        this -> a = a;
        this -> b = b;
        this -> cost = cost;
    }
    bool operator < (const muchie &other) const {
        return this -> cost > other.cost;
    }
};
vector <Vecin> G[N_MAX];
void read()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i<=m; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        G[x].pb(Vecin(y, c));
        G[y].pb(Vecin(x, c));
    }
}
bool rez[N_MAX];
priority_queue<muchie>candidates;
vector <muchie> sol;
int costsol = 0;
void init()
{
    rez[1] = 1;
    for(int i = 0; i<G[1].size(); i++)
        candidates.push(muchie(1, G[1][i].capat, G[1][i].cost));
}
void solve()
{
    while(!candidates.empty())
    {
        muchie muc = candidates.top();
        candidates.pop();
        if(!(rez[muc.a] && rez[muc.b]))
        {
            sol.pb(muc);
            costsol += muc.cost;
            int nod_nou;
            if(!rez[muc.a]) nod_nou = muc.a;
            else nod_nou = muc.b;
            for(int i = 0; i<G[nod_nou].size(); ++i)
            candidates.push(muchie(nod_nou, G[nod_nou][i].capat, G[nod_nou][i].cost));
            rez[nod_nou] = 1;
        }
    }
}
void write()
{
    printf("%d\n%d\n", costsol, sol.size());
    for(int i = 0; i<sol.size(); i++)
        printf("%d %d\n", sol[i].a, sol[i].b);

}
int main()
{
    read();
    init();
    solve();
    write();
    return 0;
}