#include <bits/stdc++.h>

using namespace std;

bool comp(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){
    if(a.first<b.first) return false;
    return true;
}

int n,m,x,y,z,cost,neg;
bool v[200005];
vector <pair<int,int>> g[200005],f;
pair<int,pair<int,int>> mn;
priority_queue <pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,function<bool(pair<int,pair<int,int>>,pair<int,pair<int,int>>)>> q(comp);

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> n >> m;
    mn={10000,{0,0}};
    for(int i=1;i<=m;i++){
        in >> x >> y >> z;
        g[x].push_back(make_pair(y,z));
        g[y].push_back(make_pair(x,z));
        if(z<mn.first) mn={z,{x,y}};
        if(z<0) cost+=z, f.push_back({x,y});
    }
    q.push(mn);
    while(q.size()){
        mn=q.top();
        q.pop();
        if(!v[mn.second.first] || !v[mn.second.second]){
            if(mn.first>=0){
                f.push_back({mn.second.first,mn.second.second});
                cost+=mn.first;
            }
            if(!v[mn.second.first]){
                v[mn.second.first]=1;
                for(int i=0;i<g[mn.second.first].size();i++){
                    if(!v[g[mn.second.first][i].first]) q.push({g[mn.second.first][i].second,{mn.second.first,g[mn.second.first][i].first}});
                }
            }
            if(!v[mn.second.second]){
                v[mn.second.second]=1;
                for(int i=0;i<g[mn.second.second].size();i++){
                    if(!v[g[mn.second.second][i].first]) q.push({g[mn.second.second][i].second,{mn.second.second,g[mn.second.second][i].first}});
                }
            }
        }
    }
    cout << cost << '\n' << f.size() << '\n';
    for(int i=0;i<f.size();i++){
        cout << f[i].first << ' ' << f[i].second << '\n';
    }
}