#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000010;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll n,m;
ll e[N<<1],ne[N<<1],h[N],tot,l[N<<1];
ll ev[N<<1],nev[N<<1],hv[N],totv,lv[N<<1];
ll ec[N<<1],nec[N<<1],hc[N],totc;

ll dfn[N],low[N],cnt;
ll Max[N],Min[N];
ll b[N],bri[N],tc;

ll a1,b1,a2,b2,id1,id2;
ll ans,p1;
ll s,t;
ll d[N],top,nw[N];
ll q[N<<1],L,R;
ll l1[N],r1[N];
vector<ll> v;
ll s1[N];

void add(ll x,ll y,ll z){
	e[++tot]=y;
	ne[tot]=h[x];
	h[x]=tot;
	l[tot]=z;
}

void addv(ll x,ll y,ll z){
//	cout<<x<<" "<<y<<" "<<z<<endl;
	ev[++totv]=y;nev[totv]=hv[x];hv[x]=totv;lv[totv]=z;
	ev[++totv]=x;nev[totv]=hv[y];hv[y]=totv;lv[totv]=0;
}

void addc(ll x,ll y){
	ec[++totc]=y;nec[totc]=hc[x];hc[x]=totc;
	ec[++totc]=x;nec[totc]=hc[y];hc[y]=totc;
}

void tarjan(ll u,ll fa){
	dfn[u]=low[u]=++cnt;
	for(int i=h[u];i!=0;i=ne[i]){
		if(e[i]==fa) continue;
		if(!dfn[e[i]]){
			tarjan(e[i],u);
			low[u]=min(low[u],low[e[i]]);
			if(low[e[i]]>dfn[u]){
				bri[i]=bri[i^1]=1;
			}
		}
		else{
			low[u]=min(low[u],dfn[e[i]]);
		}
	}
}

void dfs(ll u,ll fa,ll col){
	b[u]=col;
	for(int i=h[u];i!=0;i=ne[i]){
		if(b[e[i]]==b[u]){
			Max[col]=max(Max[col],l[i]);
			Min[col]=min(Min[col],l[i]);
		}
		if(e[i]==fa||bri[i]||b[e[i]]) continue;
		dfs(e[i],u,col);
	}
}

bool bfs(){
	memset(d,0,sizeof(d));
	L=1;R=0;
	q[++R]=s;d[s]=1;nw[s]=hv[s];
	while(L<=R){
		ll u=q[L++];
		for(int i=hv[u];i!=0;i=nev[i]){
			if(lv[i]&&!d[ev[i]]){
				q[++R]=ev[i];
				d[ev[i]]=d[u]+1;
				nw[ev[i]]=hv[ev[i]];
				if(ev[i]==t) return 1;
			}
		}
	}
	return 0;
}

ll dinic(ll u,ll flow){
	if(u==t) return flow;
	ll y=0;
	for(int i=nw[u];i!=0&&flow;i=nev[i]){
		nw[u]=i;
		if(lv[i]&&d[ev[i]]==d[u]+1){
			ll x=dinic(ev[i],min(lv[i],flow));
			if(!x) d[ev[i]]=0;
			flow-=x;y+=x;
			lv[i]-=x;lv[i^1]+=x;
		}
	}
	return y;
}

void dfs3(ll u){
	s1[u]=1;
	v.push_back(u);
	for(int i=hc[u];i!=0;i=nec[i]){
//		cout<<ec[i]<<endl;
		if(s1[ec[i]]) continue;
		dfs3(ec[i]);
		return;
	}
}

int main(){
	tot=totv=1;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		ll x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	memset(Min,0x3f,sizeof(Min));
	for(int i=1;i<=n;i++){
		if(!b[i]) dfs(i,0,++tc);
	}
//	cout<<Max[1]<<" "<<Min[1]<<" "<<tc<<endl;
	
	p1=0,ans=-1;
	for(int i=1;i<=tc;i++){
		if(Max[i]-Min[i]>ans){
			ans=Max[i]-Min[i];
//			cout<<Max[i]<<" "<<Min[i]<<" "<<ans<<endl;
			p1=i;
		}
	}
	
	top=n*2;
	s=++top;t=++top;
//	cout<<endl;
	for(int i=1;i<=n;i++){
		addv(i,i+n,1);
		if(b[i]!=p1) continue;
		for(int j=h[i];j!=0;j=ne[j]){
			if(b[e[j]]!=b[i]) continue;
			if((!a1)&&l[j]==Min[p1]){
				a1=i;b1=e[j];id1=j;
			}
			else if((!a2)&&l[j]==Max[p1]){
				a2=i;b2=e[j];id2=j;
			}
			else if((e[j]==a1&&i==b1)||(e[j]==a2&&i==b2)) continue;
			else if(i<=e[j]){
//				cout<<i<<" "<<e[j]<<endl;
				top++;top++;
				addv(i+n,top,1);
				addv(e[j]+n,top,1);
				addv(top,top-1,1);
				addv(top-1,i,1);
				addv(top-1,e[j],1);
				l1[top]=i;r1[top]=e[j];
			}
		}
	}
	
	addv(s,a1+n,1);addv(s,b1+n,1);
	addv(a2,t,1);addv(b2,t,1);
	
	ll res=0;
	while(bfs()){
		ll x=0;
		while(x=dinic(s,INF)) res+=x;
	}
//	cout<<res<<endl;
	
//	cout<<endl;
	for(int i=1;i<=n;i++){
		for(int j=hv[i+n];j!=0;j=nev[j]){
			if(ev[j]<=t) continue;
//			cout<<i+n<<" "<<ev[j]<<" "<<lv[j]<<endl;
			if(lv[j]==0){
//				cout<<i<<" "<<ev[j]<<endl;
				addc(l1[ev[j]],r1[ev[j]]);
//				cout<<l1[ev[j]]<<" "<<r1[ev[j]]<<endl;
			}
		}
	}
	addc(a1,b1);addc(a2,b2);
	
	dfs3(a1);
	
	cout<<ans<<endl;
	cout<<v.size()<<endl;
	for(int i=0;i<v.size();i++){
		cout<<v[i]<<" ";
	}
	return 0;
}
/*
5 7
1 2 1
1 3 -2
2 3 1
3 4 3
4 5 1
1 5 -1
2 5 2

7 9
1 2 0
2 6 0
3 7 -100
6 7 0
1 4 100
4 5 0
2 5 0
5 6 0
2 3 0

5 6
1 3 100
1 4 0
3 4 0
4 2 0
4 5 0
5 2 -100
1 1 1 1 1 200
*/