#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>g[100005];
int dfn[100005],low[100005],st[100005],col[100005],t1=0,t2=0;
void tarjan(int x,int la){
	dfn[x]=low[x]=++t1;
	st[++t2]=x;
	for(auto pi:g[x]){
		int cu=pi.first;
		if(cu==la)continue;
		if(!dfn[cu]){
			tarjan(cu,x);
			low[x]=min(low[x],low[cu]);
		}else{
			low[x]=min(low[x],dfn[cu]);
		}
	}
	if(dfn[x]!=low[x])return;
	int pp;
	do{
		pp=st[t2--];
		col[pp]=x;
	}while(pp!=x);
}
int mn[100005],mx[100005];
pair<int,int>zn[100005],zx[100005];
namespace MF{
	int n,S,T;
	int hd[200005],nxt[500005],c[500005],dy[500005],tot=1;
	int cur[200005],l[200005];
	void addedge(int u,int v,int w){
		nxt[++tot]=hd[u],hd[u]=tot;
		c[tot]=w,dy[tot]=v;
	}
	void adde(int u,int v,int w){
		addedge(u,v,w);addedge(v,u,0);
	}
	long long ans;
	void clear(){
		for(int i=1;i<=n;++i)hd[i]=0;
		for(int i=1;i<=tot;++i)nxt[i]=c[i]=dy[i]=0;
		tot=1;ans=0;
	}
	bool getc(){
		for(int i=1;i<=n;++i)l[i]=1e9,cur[i]=hd[i];
		l[S]=0;
		queue<int>q;
		q.emplace(S);
		while(q.size()){
			int x=q.front();
			q.pop();
			for(int i=hd[x];i;i=nxt[i]){
				if(!c[i])continue;
				int cu=dy[i];
				if(l[cu]>l[x]+1){
					l[cu]=l[x]+1;
					q.emplace(cu);
				}
			}
		}
		return l[T]<1e9;
	}
	int dinic(int x,int rl){
		if(x==T){
			ans+=rl;
			return rl;
		}
		int rr=rl;
		for(int i=cur[x];i;i=nxt[i]){
			cur[x]=i;
			if(!c[i])continue;
			int cu=dy[i];
			if(l[cu]!=l[x]+1)continue;
			int zz=dinic(cu,min(rr,c[i]));
			c[i]-=zz,c[i^1]+=zz;
			rr-=zz;
			if(!rr)break;
		}
		return rl-rr;
	}
}
set<int>gg[100005];
void jia(int x,int y){
	gg[x].emplace(y);
	gg[y].emplace(x);
}
void dfs(int x,int fl){
	while(gg[x].size()){
		int y=*(gg[x].begin());
		gg[x].erase(y);gg[y].erase(x);
		dfs(y,1);
	}
	if(fl)printf("%d ",x);
}
void oula(int n){
	int r=0,he=0;
	for(int i=1;i<=n;++i){
		if(gg[i].size())r=i;
		he+=gg[i].size();
	}
	printf("%d\n",he/2);
	dfs(r,0);
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].emplace_back(v,w);
		g[v].emplace_back(u,w);
	}
	tarjan(1,0);
	for(int i=1;i<=n;++i)mn[i]=1e9+7,mx[i]=-1e9-7;
	for(int i=1;i<=n;++i)for(auto pi:g[i]){
		int cu=pi.first,c2=pi.second;
		if(col[i]!=col[cu]||i>cu)continue;
		int c=col[i];
		if(mn[c]>c2)mn[c]=c2,zn[c]=make_pair(i,cu);
		if(mx[c]<=c2)mx[c]=c2,zx[c]=make_pair(i,cu);
	}
	int zd=-1,wz=0;
	pair<int,int>p1,p2;
	for(int i=1;i<=n;++i)if(mx[i]>=mn[i]){
		if(zd<mx[i]-mn[i]){
			zd=mx[i]-mn[i];wz=i;
			p1=zx[i];p2=zn[i];
		}
	}
	MF::n=n+2,MF::S=n+1,MF::T=n+2;
	for(int i=1;i<=n;++i)for(auto pi:g[i]){
		int cu=pi.first;
		if(col[i]!=wz||col[cu]!=wz||i>cu)continue;
		if(i==p1.first&&cu==p1.second)continue;
		if(i==p2.first&&cu==p2.second)continue;
		MF::addedge(i,cu,1);MF::addedge(cu,i,1);
	}
	MF::addedge(n+1,p1.first,1);MF::addedge(p1.first,n+1,0);
	MF::addedge(n+1,p1.second,1);MF::addedge(p1.second,n+1,0);
	MF::addedge(p2.first,n+2,1);MF::addedge(n+2,p2.first,0);
	MF::addedge(p2.second,n+2,1);MF::addedge(n+2,p2.second,0);
	while(MF::getc())MF::dinic(MF::S,INT_MAX);
	printf("%d\n",zd);
	jia(p1.first,p1.second);
	jia(p2.first,p2.second);
	for(int i=1;i<=n;++i){
		for(int j=MF::hd[i];j;j=MF::nxt[j]){
			if(MF::c[j])continue;
			int cu=MF::dy[j];
			if(cu>n)continue;
			jia(i,cu);
		}
	}
	oula(n);
	return 0;
}