#include<bits/stdc++.h>
#define int long long
#define pr(x,y) make_pair(x,y)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int buf[30];
inline void print(int x,char ch=' '){
	if(x<0) putchar('-'),x=-x;
	int tot=0;
	do{
		buf[++tot]=x%10;
		x/=10;
	}while(x);
	for(int i=tot;i;i--)
		putchar(buf[i]+'0');
	putchar(ch);
}
const int MAXN=1e6+5;
int n,m;
int head[MAXN],to[MAXN],nxt[MAXN],val[MAXN],tot=1;
bool del[MAXN];
void add(int u,int v,int w){
	nxt[++tot]=head[u];
	to[tot]=v,val[tot]=w;
	head[u]=tot;
}
int dfn[MAXN],low[MAXN],num;
void tarjan(int x,int fa){
	dfn[x]=low[x]=++num;
	for(int i=head[x];i;i=nxt[i]){
		if(!dfn[to[i]]){
			tarjan(to[i],i);
			low[x]=min(low[x],low[to[i]]);
			if(low[to[i]]>dfn[x])
				del[i]=del[i^1]=1;
		}
		else if(i!=(fa^1))
			low[x]=min(low[x],dfn[to[i]]);
	}
}
int fa[MAXN];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
set<pair<int,int>> s[MAXN];

struct max_flow{
	int head[MAXN],to[MAXN],nxt[MAXN],flow[MAXN],tot=1;
	void add(int u,int v){
		nxt[++tot]=head[u];
		to[tot]=v,flow[tot]=1;
		head[u]=tot;
		
		nxt[++tot]=head[v];
		to[tot]=u,flow[tot]=0;
		head[v]=tot;
	}
	int pre[MAXN];
	bool vis[MAXN];
	void bfs(int fst){	
		queue<int> q;
		q.push(fst);
		memset(vis,0,sizeof(vis));
		memset(pre,0,sizeof(pre));
		vis[fst]=1;
		while(!q.empty()){
			int x=q.front();
			q.pop();
			for(int i=head[x];i;i=nxt[i]){
				if(!vis[to[i]]&&flow[i]){
					pre[to[i]]=i;
					vis[to[i]]=1;
					q.push(to[i]);
				}
			}
		}
	}
	vector<int> ek(){
		vector<int> ans;
		bfs(n+1);
		int pos=n+2;
		while(pos){
			ans.push_back(pos);
			int x=pre[pos];
			flow[x]--,flow[x^1]++;
			pos=to[x^1];
		}
		return ans;
	}
}temp;
void solve(int u1,int v1,int u2,int v2){
	for(int x=1;x<=n;x++)
		for(int i=head[x];i;i=nxt[i]){
			if(pr(x,to[i])!=pr(u1,v1)&&
			   pr(x,to[i])!=pr(v1,u1)&&
			   pr(x,to[i])!=pr(u2,v2)&&
			   pr(x,to[i])!=pr(v2,u2))
				temp.add(x,to[i]);
		}		
	temp.add(n+1,u1);
	temp.add(n+1,v1);
	temp.add(u2,n+2);
	temp.add(v2,n+2); 
	vector<int> ans,stk;
	ans=temp.ek();
	for(int i=1;i<ans.size()-1;i++) stk.push_back(ans[i]);
	ans=temp.ek();
	reverse(ans.begin(),ans.end());
	for(int i=1;i<ans.size()-1;i++) stk.push_back(ans[i]);
	print(stk.size(),'\n');
	for(auto x:stk) print(x);
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		add(u,v,w),add(v,u,w);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i,0);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=2;i<=tot;i+=2)
		if(!del[i]) fa[to[i]]=find(fa[to[i^1]]);
	int ans=-1,ansu,ansv;
	for(int i=2;i<=tot;i+=2){
		if(find(to[i])==find(to[i^1])){
			int x=find(to[i]);
			s[x].insert(pr(val[i],i)); 
		}
	}
	for(int x=1;x<=n;x++){
		if(!s[x].empty()){
			int mn=s[x].begin()->first,mx=(--s[x].end())->first;
			if(mx-mn>ans){
				ans=mx-mn;
				ansu=s[x].begin()->second;
				ansv=(--s[x].end())->second;
			}
		}
	}
	print(ans,'\n');
	solve(to[ansu],to[ansu^1],to[ansv],to[ansv^1]); 
	return 0;
}