#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <functional>
constexpr int N(100010),inf(1.01e9);
using t3i=std::tuple<int,int,int,int>;
using veci=std::vector<int>;
int bcnt,n,m;
t3i mxm[N],mnm[N];
veci pts[N],ts[N<<1],gs[N];
#define DEBUG {if(n==99997) std::cout<<__FUNCTION__<<std::endl;}
std::vector<std::pair<int,int>> eds[N],es[N];
void tarjan(int u)
{
	static std::tuple<int,int,int> stk[N];
	static int top,dfn[N],low[N],dcnt;
	dfn[u]=low[u]=++dcnt;stk[++top]={u,-1,-1};
	for(auto [v,w]:es[u])
	{
		if(!dfn[v])
		{
			tarjan(v);low[u]=std::min(low[u],low[v]);
			if(low[v]==dfn[u])
			{
				int k=++bcnt;
				pts[k].emplace_back(u);
				mxm[k]={-inf,0,0,0},mnm[k]={inf,0,0,0};
				while(1)
				{
					auto [x,y,w]=stk[top--];
					// std::cerr<<x<<" "<<y<<" "<<w<<std::endl;
					if(~y) eds[k].emplace_back(x,y),mxm[k]=std::max(mxm[k],{w,x,y,k+n}),mnm[k]=std::min(mnm[k],{w,x,y,k+n});
					else
					{
						pts[k].emplace_back(x);
						if(x==v) break;
					}
				}
				if(eds[k].size()>1)
				{
					for(int v:pts[k]) ts[k+n].emplace_back(v),ts[v].emplace_back(k+n);
				}
			}
		}
		else if(dfn[v]<dfn[u]) stk[++top]={u,v,w},low[u]=std::min(low[u],dfn[v]);
	}
}
std::pair<veci,veci> calc(const veci &vs,const veci &vall)
{
	DEBUG;
	int l=vs.size(),u=vs[0],v=vs[l-1];
	static int fu[N],fv[N];
	static bool mk[N];
	for(int i:vall) fu[i]=fv[i]=0,mk[i]=false;
	for(int k:vs) mk[k]=true;
	std::function<void(int,int,int*)> dfs=[&dfs](int u,int fa,int *ff){ff[u]=fa;if(mk[u]) return;for(int v:gs[u]) if(!ff[v]) dfs(v,u,ff);};
	fu[u]=-1;for(int k:gs[u]) if(!mk[k] && !fu[k]) dfs(k,u,fu);
	fv[v]=-1;for(int k:gs[v]) if(!mk[k] && !fv[k]) dfs(k,v,fv);
	// std::cerr<<"❤"<<std::endl;
	if(fv[u])
	{
		if(n==99997) std::cout<<"❤gyc"<<std::endl;
		veci res;
		for(int i(u);~i;i=fv[i]) res.emplace_back(i);
		// std::cerr<<"end"<<std::endl;
		return {vs,res};
	}
	int p1(1);while(!fv[vs[p1]]) ++p1;
	int p2(p1+1);while(!fu[vs[p2]]) ++p2;
	veci r1;for(int i(vs[p2]);~i;i=fu[i]) r1.emplace_back(i);std::reverse(r1.begin(),r1.end());r1.insert(r1.begin(),vs.begin()+p2+1,vs.end());
	veci r2;r2.insert(r2.begin(),vs.begin(),vs.begin()+p1);for(int i(vs[p1]);~i;i=fv[i]) r2.emplace_back(i);
	for(int i(0);i<std::min<int>(5,r1.size());++i) std::cout<<r1[i]<<" ";std::cout<<std::endl;
	for(int i(0);i<std::min<int>(5,r2.size());++i) std::cout<<r2[i]<<" ";std::cout<<std::endl;
	return {r1,r2};
}
veci solve_path(veci pts,int u,int v,int frb,int pre)
{
	DEBUG;
	static int fs[N];
	static bool vis[N];
	fs[pre]=0;
	std::function<void(int,int)> dfs=[&](int u,int fa)->void{fs[u]=fa;vis[u]=true;for(int v:gs[u]) if(!vis[v] && v!=frb) dfs(v,u);};
	dfs(v,pre);
	veci ret;
	for(int k:pts) vis[k]=false;
	for(int i(u);i;i=fs[i]) ret.emplace_back(i);
	return ret;
}
std::pair<veci,veci> solve1(int idx,int u,int v,int s)
{
	DEBUG;
	idx-=n;
	for(auto [u,v]:eds[idx]) gs[u].emplace_back(v),gs[v].emplace_back(u);
	std::pair<veci,veci> res;
	if(u==s)
	{
		res=calc({s,v},pts[idx]);
	}
	else
	{
		res=calc(solve_path(pts[idx],s,v,u,u),pts[idx]);
	}
	for(int u:pts[idx]) gs[u].clear();
	return res;
}
std::pair<veci,veci> solve2(int idx,int u,int v)
{
	DEBUG;
	idx-=n;
	for(auto [u,v]:eds[idx]) gs[u].emplace_back(v),gs[v].emplace_back(u);
	auto res=calc(solve_path(pts[idx],u,v,0,0),pts[idx]);
	for(int u:pts[idx]) gs[u].clear();
	return res;
}
veci solve3(int idx,int u,int v,int s,int t)
{
	DEBUG;
	idx-=n;
	for(auto [u,v]:eds[idx]) gs[u].emplace_back(v),gs[v].emplace_back(u);
	auto hp=[](std::pair<veci,veci> pr,veci vall)->veci
	{
		auto [p1,p2]=pr;
		std::reverse(p2.begin(),p2.end());
		p1.pop_back();p2.pop_back();
		p1.insert(p1.end(),p2.begin(),p2.end());
		for(int v:vall) gs[v].clear();
		return p1;
	};
	if(v==s || v==t) return hp(calc({u,v,(s^t^v)},pts[idx]),pts[idx]);
	else if(u==s || u==t) return hp(calc({v,u,(s^t^u)},pts[idx]),pts[idx]);
	auto pt=solve_path(pts[idx],v,s,t,t);
	int hu=-1,len=pt.size();
	for(int k(0);k<len;++k) if(pt[k]==u){hu=k;break;}
	if(n==99997) std::cout<<hu<<std::endl;
	if(~hu)
	{
		pt.erase(pt.begin()+1,pt.begin()+hu);
	}
	else pt.insert(pt.begin(),u);
	for(int i=0;i<std::min<int>(pt.size(),10);++i) std::cout<<pt[i]<<" ";std::cout<<std::endl;
	return hp(calc(pt,pts[idx]),pts[idx]);
}
int main()
{
	DEBUG;
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cin>>n>>m;
	for(int i(1),u,v,w;i<=m;++i) std::cin>>u>>v>>w,es[u].emplace_back(v,w),es[v].emplace_back(u,w);
	tarjan(1);
	static bool vis[N<<1];
	std::function<void(int,t3i&,t3i&)> dfs1=[&dfs1](int u,t3i &mx,t3i &mn)->void
	{
		if(u>n) mx=std::max(mxm[u-n],mx),mn=std::min(mnm[u-n],mn);vis[u]=true;
		for(int v:ts[u]) if(!vis[v]) dfs1(v,mx,mn);
	};
	int ans=-1,su,sv,sk,tu,tv,tk;
	for(int i(1);i<=n;++i) if(!vis[i] && ts[i].size())
	{
		t3i mn{inf,0,0,0},mx{-inf,0,0,0};
		dfs1(i,mx,mn);
		auto [w1,e1u,e1v,v1]=mn;auto [w2,e2u,e2v,v2]=mx;
		if(w2-w1>ans)
		{
			ans=w2-w1;
			su=e1u;sv=e1v;sk=v1;
			tu=e2u;tv=e2v;tk=v2;
		}
	}
	std::cout<<ans<<std::endl;
	if(sk!=tk)
	{
		static int ff[N<<1];
		std::function<void(int,int)> dfs2=[&dfs2](int u,int fa)->void{ff[u]=fa;for(int v:ts[u])if(fa!=v) dfs2(v,u);};
		dfs2(tk,0);
		static int vs[N<<1],vc;
		for(int i(tk);i;i=ff[i]) vs[++vc]=i;
		auto [r1,r2]=solve1(sk,su,sv,vs[2]);
		for(int i=3;i<vc;i+=2)
		{
			auto [c1,c2]=solve2(vs[i],vs[i-1],vs[i+1]);
			c1.erase(c1.begin());c2.erase(c2.begin());
			r1.insert(r1.end(),c1.begin(),c1.end());
			r2.insert(r2.end(),c2.begin(),c2.end());
		}
		auto [c1,c2]=solve1(tk,tu,tv,vs[vc-1]);
		std::reverse(c1.begin(),c1.end());std::reverse(c2.begin(),c2.end());
		c1.erase(c1.begin());c2.erase(c2.begin());
		r1.insert(r1.end(),c1.begin(),c1.end());
		r2.insert(r2.end(),c2.begin(),c2.end());
		std::reverse(r2.begin(),r2.end());r1.erase(r1.end());r2.erase(r2.end());
		r1.insert(r1.end(),r2.begin(),r2.end());
		std::cout<<r1.size()<<std::endl;
		for(int v: r1) std::cout<<v<<" ";std::cout<<std::endl;
	}
	else
	{
		auto r1=solve3(sk,su,sv,tu,tv);
		std::cout<<r1.size()<<std::endl;
		for(int v:r1) std::cout<<v<<" ";std::cout<<std::endl;
	}
	return 0;
}