#include <fstream>
#include <vector>
#include <queue>
#define Nmax 400005
#define INF 1e9 + 5
using namespace std;

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

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

struct cmp {
    bool operator() (const muchie a,const muchie b) {
        return a.c > b.c;
    }
};

bool vizitat[Nmax];
int n,m,d[Nmax];
vector <pair <int,int>> v[Nmax];

int main() {
    in>>n>>m;
    for (int i=1;i <= m;++i) {
        int x,y,c;
        in>>x>>y>>c;

        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }

    for (int i=1;i <= n;++i) {
        d[i] = INF;
    }

    vector< pair<int,int> > edges;

    int totalCost = 0;

    priority_queue<muchie,vector<muchie>,cmp> pq;

    pq.push( {0,1,0} );
    d[1] = 0;

    while (pq.size()) {
        muchie m = pq.top();
        pq.pop();
        int node = m.y;

        if (vizitat[node] || d[node] < m.c) {
            continue;
        }
        vizitat[node] = true;
        edges.push_back({m.x,m.y});
        totalCost += m.c;

        for (auto p : v[node]) {
            int nxt = p.first, currentCost = p.second;
            if (vizitat[nxt] || d[nxt] <= currentCost) {
                continue;
            }
            d[nxt] = currentCost;
            pq.push( {node,nxt,currentCost} );
        }
    }

    out<<totalCost<<'\n'<<n-1<<'\n';
    for(int i=1;i<edges.size();i++)
        out<<edges[i].first<<" "<<edges[i].second<<'\n';
    return 0;
}