#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];

ll tmp;

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,ll w){
//	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]=w;
}

void addc(ll x,ll y){
	tmp++;
	if((x==24822&&y==39127)||(x==39127&&y==24822)){
		puts("114514!!!!!!!!!!!!");
	}
	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]])){
				d[ev[i]]=d[u]+1;
				nw[ev[i]]=hv[ev[i]];
				if(ev[i]==t) return 1;
				q[++R]=ev[i];
			}
		}
	}
	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,ll num){
	ll tag=0;
	for(int i=hc[u];i!=0;i=nec[i]){
		if(s1[i]&&s1[i^1]) continue;
		s1[i]=s1[i^1]=1;
		dfs3(ec[i],num+1);
		tag=1;
//		return;
	}
	v.push_back(u);
	return;
}

int main(){
	tot=totv=totc=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++){
		Max[i]=-INF;Min[i]=INF;
		if(!dfn[i]) tarjan(i,0);
	}
	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];
			p1=i;
		}
	}
	
	top=n+1;
	s=++top;t=++top;
//	cout<<endl;
	for(int i=1;i<=n;i++){
		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;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(b[i]!=p1) continue;
		for(int j=h[i];j!=0;j=ne[j]){
			if(b[e[j]]!=b[i]) continue;
			if(i==a1&&e[j]==b1) continue;
			if(i==b1&&e[j]==a1) continue;
			if(i==a2&&e[j]==b2) continue;
			if(i==b2&&e[j]==a2) continue;
			
			if(i<e[j]){
				addv(i,e[j],1,1);
			}
		}
	}
	
	addv(s,a1,1,0);addv(s,b1,1,0);
	addv(a2,t,1,0);addv(b2,t,1,0);
	
	ll res=0;
	while(bfs()){
		ll x=0;
		while(x=dinic(s,INF)) res+=x;
	}
//	cout<<res<<endl;
	
//	cout<<endl;
	for(int i=2;i<=totv;i+=2){
		if(lv[i]!=1){
			ll x=ev[i],y=ev[i^1];
			if(x==s||x==t||y==s||y==t) continue;
			addc(x,y);
		}
	}
	addc(a1,b1);addc(a2,b2);
	if(n==99996&&m==100000) cout<<tmp<<endl;
	cout<<ans<<endl;
	dfs3(a1,1);
	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

6 7
1 2 0
1 3 100
2 3 0
2 5 -10000
4 5 0
2 4 0
5 6 200

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