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

ll n,m;
ll e[N<<1],ne[N<<1],h[N],tot,l[N<<1];
ll dfn[N],low[N],cnt;
ll Max[N],Min[N];
ll b[N],s[N],tc;

ll a1,b1,a2,b2,id1,id2;
ll s2[N],s3[N];
ll ans,p1;
vector<ll> v1,v2;

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

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]){
				s[i]=s[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||s[i]||b[e[i]]) continue;
		dfs(e[i],u,col);
	}
}

bool dfs2(ll u,ll fa){
	if(u==a2) return 1;
	s3[u]=1;
	for(int i=h[u];i!=0;i=ne[i]){
		if(e[i]==fa||s[i]||s2[i]||s3[e[i]]) continue;
		s2[i]=s2[i^1]=1;
		if(dfs2(e[i],u)){
			v1.push_back(u);
			return 1;
		}
		s2[i]=s2[i^1]=0;
	}
	return 0;
}

bool dfs3(ll u,ll fa){
	if(u==b1) return 1;
	s3[u]=1;
	for(int i=h[u];i!=0;i=ne[i]){
		if(e[i]==fa||s[i]||s2[i]||s3[e[i]]) continue;
		s2[i]=s2[i^1]=1;
		if(dfs3(e[i],u)){
			v2.push_back(u);
			return 1;
		}
		s2[i]=s2[i^1]=0;
	}
	return 0;
}

bool check(){
	memset(s2,0,sizeof(s2));v1.clear();v2.clear();
	s2[id1]=s2[id2]=s2[id1^1]=s2[id2^1]=1;
	memset(s3,0,sizeof(s3));
	dfs2(a1,0);
	memset(s3,0,sizeof(s3));
	if(!dfs3(b2,0)) return 0;
	
	ll num=2+v1.size()+v2.size();
//	if(a1==a2) num--;
//	if(b1==b2) num--;
//	cout<<v1.size()<<" "<<v2.size()<<endl;
	cout<<ans<<endl;
	cout<<num<<endl;
	cout<<a1<<" ";
	for(int i=v1.size()-2;i>=0;i--) cout<<v1[i]<<" ";
	if(a2!=a1) cout<<a2<<" ";
//	cout<<endl;
	cout<<b2<<" ";
	for(int i=v2.size()-2;i>=0;i--) cout<<v2[i]<<" ";
	if(b1!=b2) cout<<b1<<" ";
	return 1;
}

int main(){
	tot=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;
		}
	}
	
	for(int i=1;i<=n;i++){
		if(b[i]!=p1) continue;
		for(int j=h[i];j!=0;j=ne[j]){
			if((!a1)&&l[j]==Min[p1]){
				if(i==a2&&e[j]==b2) continue;
				if(e[j]==a2&&i==b2) continue;
				a1=i;b1=e[j];id1=j;
			}
			if((!a2)&&l[j]==Max[p1]){
				if(i==a1&&e[j]==b1) continue;
				if(e[j]==a1&&i==b1) continue;
				a2=i;b2=e[j];id2=j;
			}
		}
	}
//	cout<<a1<<" "<<b1<<" "<<a2<<" "<<b2<<endl;
	if(check()) return 0;
	swap(a2,b2);
	check();
	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
*/