#include<bits/stdc++.h>
#define int long long
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=1e5+5,inf=1e18;
int n,m;
int head[MAXN],to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1],tot=1;
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;
bool del[MAXN<<1];
void tarjan(int x,int y){
	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!=(y^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]);
}
void merge(int u,int v){
	fa[find(u)]=find(v);
} 
int mx[MAXN],mn[MAXN],mxid[MAXN],mnid[MAXN];

struct max_flow{
	int head[MAXN],to[MAXN<<2],nxt[MAXN<<2],flow[MAXN<<2],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(){
		queue<int> q;
		q.push(n+1);
		for(int i=1;i<=n+2;i++)
			vis[i]=0,pre[i]=0;
		vis[n+1]=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]){
					vis[to[i]]=1;
					pre[to[i]]=i;
					q.push(to[i]);
				}
			}
		}
	}
	vector<int> EK(){
		bfs();
		vector<int> ans;
		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;
	} 
}mf;
void solve(int ansu,int ansv){
	for(int x=1;x<=n;x++)
		for(int i=head[x];i;i=nxt[i])
			if(i!=ansu&&i!=ansv&&i!=(ansu^1)&&i!=(ansv^1))
				mf.add(x,to[i]);
	mf.add(n+1,to[ansu]);
	mf.add(n+1,to[ansu^1]);
	mf.add(to[ansv],n+2);
	mf.add(to[ansv^1],n+2);
	vector<int> ans=mf.EK(),temp;
	for(int i=ans.size()-2;i>0;i--) temp.push_back(ans[i]);
	ans=mf.EK();
	for(int i=1;i<ans.size()-1;i++) temp.push_back(ans[i]);
	print(temp.size(),'\n');
	for(auto x:temp) 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 x=1;x<=n;x++)
		for(int i=head[x];i;i=nxt[i])
			if(!del[i]) merge(x,to[i]);
	for(int i=1;i<=n;i++)
		mx[i]=-inf,mn[i]=inf;
	for(int x=1;x<=n;x++)
		for(int i=head[x];i;i=nxt[i])
			if(!del[i]){
				int y=find(x);
				if(val[i]>mx[y])
					mx[y]=val[i],mxid[y]=i;
				if(val[i]<mn[y])
					mn[y]=val[i],mnid[y]=i;
			}
			
	int ans=0,ansu,ansv;
	for(int i=1;i<=n;i++)
		if(mx[i]-mn[i]>ans){
			ans=mx[i]-mn[i];
			ansu=mxid[i];
			ansv=mnid[i];
		}
	print(ans,'\n');
	solve(ansu,ansv);
	return 0;
}