#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <functional>
constexpr int N(400010),inf(1.01e9);
using t3i=std::tuple<int,int,int,int>;
using veci=std::vector<int>;
#define eb emplace_back
#define bg begin
#define ed end
int bcnt,n,m;
t3i mxm[N],mnm[N];
veci pts[N],ts[N<<1],gs[N];
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].eb(u);
				mxm[k]={-inf,0,0,0},mnm[k]={inf,0,0,0};
				while(1)
				{
					auto [x,y,w]=stk[top--];
					if(~y) eds[k].eb(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].eb(x);
						if(x==v) break;
					}
				}
				if(eds[k].size()>1)
				{
					for(int v:pts[k]) ts[k+n].eb(v),ts[v].eb(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)
{
	int l(vs.size()),u(vs[0]),v(vs[l-1]),k(vs[1]);
	static int idx[N];
	for(int i:vall) idx[i]=-1;
	for(int i(0);i<l;++i) idx[vs[i]]=i;
	veci r1({u}),r2({u,k});int p1(u),p2(k);
	static int fa1[N],fa2[N];
	static bool vis1[N],vis2[N];
	for(int i:vall) vis1[i]=vis2[i]=false,fa1[i]=fa2[i]=0;
	int *f1(fa1),*f2(fa2);bool *v1(vis1),*v2(vis2);
	if(v==k)
	{
		std::function<void(int,int)> dfs=[&](int u,int fa)->void{v1[u]=true;f1[u]=fa;for(int t:gs[u]) if(!v1[t]) dfs(t,u);};
		v1[u]=true;
		for(int t:gs[u]) if(t!=v && !v1[t]) dfs(t,u);
		r1.clear();for(int t(v);t;t=f1[t]) r1.eb(t);std::reverse(r1.bg(),r1.ed());
	}
	else{
		while(1)
		{
			if(idx[p1]>idx[p2]) std::swap(p1,p2),std::swap(f1,f2),std::swap(v1,v2),r1.swap(r2);
			if(p2==v)
			{
				for(int i(idx[p1]+1);i<l;++i) r1.eb(vs[i]);
				break;
			}
			int mxi(-1);
			std::function<void(int,int)> dfs=[&](int u,int fa)->void{v1[u]=true;f1[u]=fa;mxi=std::max(mxi,idx[u]);if(idx[u]>=idx[p2]) return;
				for(int t:gs[u]) if(!v1[t] && !(idx[u]==-1 && (~idx[t] && idx[t]<idx[p2]))) dfs(t,u);};
			dfs(p1,0);
			int len(r1.size());
			for(int t(vs[mxi]);t!=p1;t=f1[t]) r1.eb(t);
			std::reverse(r1.bg()+len,r1.ed());
			p1=vs[mxi];
		}
	}
	return {r1,r2};
}
veci solve_path(veci pts,int u,int v,int frb,int pre)
{
	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.eb(i);
	return ret;
}
std::pair<veci,veci> solve1(int idx,int u,int v,int s)
{
	idx-=n;
	for(auto [u,v]:eds[idx])
	{
		gs[u].eb(v),gs[v].eb(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)
{
	idx-=n;
	for(auto [u,v]:eds[idx]) gs[u].eb(v),gs[v].eb(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)
{
	idx-=n;
	for(auto [u,v]:eds[idx])
	{
		gs[u].eb(v),gs[v].eb(u);
	}
	auto hp=[](std::pair<veci,veci> pr,veci vall)->veci
	{
		auto [p1,p2]=pr;
		std::reverse(p2.bg(),p2.ed());
		p1.pop_back();p2.pop_back();
		p1.insert(p1.ed(),p2.bg(),p2.ed());
		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(~hu)
	{
		pt.erase(pt.bg()+1,pt.bg()+hu);
	}
	else pt.insert(pt.bg(),u);
	return hp(calc(pt,pts[idx]),pts[idx]);
}
int main()
{
	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].eb(v,w),es[v].eb(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(sk);i;i=ff[i]) vs[++vc]=i;
		auto [r1,r2]=solve1(sk,su,sv,vs[2]);
		std::reverse(r1.bg(),r1.ed());std::reverse(r2.bg(),r2.ed());
		for(int i=3;i<vc;i+=2)
		{
			auto [c1,c2]=solve2(vs[i],vs[i-1],vs[i+1]);
			c1.erase(c1.bg());c2.erase(c2.bg());
			r1.insert(r1.ed(),c1.bg(),c1.ed());
			r2.insert(r2.ed(),c2.bg(),c2.ed());
		}
		auto [c1,c2]=solve1(tk,tu,tv,vs[vc-1]);
		c1.erase(c1.bg());c2.erase(c2.bg());
		r1.insert(r1.ed(),c1.bg(),c1.ed());
		r2.insert(r2.ed(),c2.bg(),c2.ed());
		std::reverse(r2.bg(),r2.ed());r1.erase(--r1.ed());r2.erase(--r2.ed());
		r1.insert(r1.ed(),r2.bg(),r2.ed());
		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;
}