// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 600005
#define inf 0x3f3f3f3f

namespace flow{

int n,s,t,maxflow;
int dep[maxn],cur[maxn];
int tot=1,head[maxn];
struct edge{
	int to,nxt,w;
}e[maxn<<1];
void adde(int u,int v,int w){
	e[++tot]=(edge){v,head[u],w};
	head[u]=tot;
}
void add(int u,int v,int w){
//	cout<<"add "<<u<<" "<<v<<" "<<w<<"\n";
	adde(u,v,w);
	adde(v,u,0);
}
bool bfs(int s,int t)
{
	queue<int>q;
	For(i,0,n)cur[i]=head[i],dep[i]=inf;
	dep[s]=0;q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(dep[v]==inf&&e[i].w){
				dep[v]=dep[u]+1;
				if(v==t)return 1;
				q.push(v);
			}
		}
	}return dep[t]<inf;
}
int dfs(int u,int t,int minn)
{
	if(!minn||u==t)return minn;
	int res=0;
	for(int i=cur[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		cur[u]=i;
		if(dep[v]!=dep[u]+1)continue;
		int flow=dfs(v,t,min(minn,e[i].w));
		if(!flow)continue;
		res+=flow,minn-=flow;
		e[i].w-=flow,e[i^1].w+=flow;
		if(!minn)break;
	}
	if(!res) dep[u]=0;
	return res;
}
inline int dinic(int s,int t)
{
	int maxflow=0,flow=0;
	while(bfs(s,t))while(flow=dfs(s,t,inf))maxflow+=flow;
	return maxflow;
}
inline void init(int N,int S,int T){
	n=N,s=S,t=T,tot=1,maxflow=0;
	For(i,0,n)head[i]=0;
}

}
using flow::add;

int n,m;

struct edge{
    int to,nxt,w;
}e[maxn<<1];
int head[maxn],tot=1;
inline void adde(int u,int v,int w){
    e[++tot]=(edge){v,head[u],w};
    head[u]=tot;
}

int dfn[maxn],low[maxn],bel[maxn],idx,scc,stk[maxn],tp;
int mn[maxn],mx[maxn];
bool cut[maxn<<1];
vi g[maxn];
void tar(int u,int lste){
    dfn[u]=low[u]=++idx,stk[++tp]=u;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(i==(lste^1))continue;
        if(!dfn[v])tar(v,i),low[u]=min(low[u],low[v]),cut[i]=cut[i^1]=low[v]>dfn[u];
        else low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        int v; ++scc;
        do v=stk[tp--],bel[v]=scc,g[scc].pb(v);while(v^u);
    }
}

int id;
vi buc[maxn];
void solve()
{
	cout<<mx[id]-mn[id]<<"\n";
	int u1,v1,u2,v2,id1=-1,id2;
	For(u,1,n)
        for(int i=head[u];i;i=e[i].nxt)
            if(bel[u]==id && bel[e[i].to]==id){
                if(id1==-1 && e[i].w==mn[id]) u1=u,v1=e[i].to,id1=i;
                else if(e[i].w==mx[id]) u2=u,v2=e[i].to,id2=i;
            }
    int s=0,t=n+1; flow::init(t,s,t);
	add(s,u1,1),add(s,v1,1);
	add(u2,t,1),add(v2,t,1);
	int fir=flow::tot;
	For(u,1,n)
        for(int i=head[u];i;i=e[i].nxt)
        	if(bel[u]==id && bel[e[i].to]==id && i!=id1 && i!=id2 && (i^1)!=id1 && (i^1)!=id2)
        		add(u,e[i].to,1);
    int fl=flow::dinic(s,t);
 //   cout<<"flow "<<fl<<"\n";
    assert(fl==2);
    vi o1,o2;
    For(i,fir+1,flow::tot)
    	if(i%2==0 && !flow::e[i].w) buc[flow::e[i^1].to].pb(flow::e[i].to);//cout<<flow::e[i^1].to<<" "<<flow::e[i].to<<'\n';
    int x=u1;
    o1.pb(x);
    while(x!=u2 && x!=v2){
    	assert(buc[x].size());
    	int y=buc[x].back(); buc[x].pop_back(); 
    	o1.pb(x=y);
	}
	x=v1;
	o2.pb(x);
	while(x!=(u2^v2^o1.back())){
		assert(buc[x].size());
		int y=buc[x].back(); buc[x].pop_back();
		o2.pb(x=y); 
	}
	while(o2.size()) o1.pb(o2.back()),o2.pop_back();
	For(i,1,n) assert(!buc[i].size());
	cout<<o1.size()<<"\n"; for(auto x:o1) cout<<x<<" "; exit(0);
}

signed main()
{
	n=read(),m=read();
    For(i,1,m){
        int u=read(),v=read(),w=read();
        adde(u,v,w),adde(v,u,w);
    }
    For(i,1,n)if(!dfn[i])tar(i,0);
    For(i,1,scc)mn[i]=inf,mx[i]=-inf;
    For(u,1,n)
        for(int i=head[u];i;i=e[i].nxt)
            if(bel[u]==bel[e[i].to]){
                mn[bel[u]]=min(mn[bel[u]],e[i].w);
                mx[bel[u]]=max(mx[bel[u]],e[i].w);
            }
    id=1;
    For(i,1,scc)if(mx[i]-mn[i]>mx[id]-mn[id])id=i;
    solve();
    
	return 0;
}