#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct muchie
{
	int x,y,c;
	inline bool operator<(const muchie &other) const
	{
		return c<other.c;
	}
} a[400005];
class DisjointSets
{
    private:
        vector<int> t,h;
        int Dad(int u)
        {
            return u==t[u]?u:t[u]=Dad(t[u]);
        }
    public:
        DisjointSets(int n)
        {
            t.push_back(0);h.push_back(0);
            for(int i=1;i<=n;i++)
            {
                h.push_back(1);
                t.push_back(i);
            }
        }
        void update(int x,int y)
        {
            x=Dad(x);y=Dad(y);
            if(x==y) return;
            if(h[x]==h[y])
            {
                h[x]++;
                t[y]=x;
            }
            else if(h[x]>h[y])
                t[y]=x;
            else
                t[x]=y;
        }
        bool query(int x,int y)
        {
            return Dad(x)==Dad(y);
        }
};
vector<int> sol;
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
	sort(a+1,a+m+1);
	DisjointSets S(n);
	int k=0,cost=0;
	for(int i=1;i<=m;i++)
		if(!S.query(a[i].x,a[i].y))
		{
			k++;
			sol.push_back(i);
			S.update(a[i].x,a[i].y);
			cost+=a[i].c;
		}
	printf("%d\n",cost);
	printf("%d\n",k);
	for(int i=0;i<k;i++)
		printf("%d %d\n",a[sol[i]].x,a[sol[i]].y);
	return 0;
}