#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=1e5+5;
int n,m,dfn[N],low[N],idx,scc,bl[N],mn[N],mx[N],id,ans,st[N],tp=0;
struct Edge{int v,w;};
vector<Edge> G[N];
vector<int> Ans;

void tarjan(int u,int fa){
  dfn[u]=low[u]=++idx,st[++tp]=u;
  for(auto i:G[u]){
    int v=i.v;
    if(!dfn[v]) tarjan(v,u),low[u]=min(low[u],low[v]);
    else if(v!=fa) low[u]=min(low[u],dfn[v]);
  }
  if(low[u]==dfn[u]){
  	++scc;int x;
  	while((x=st[tp--])){
  	  bl[x]=scc;
  	  if(x==u) break;
	}
  }
}

namespace MF{
  int head[N],tot=1,lv[N],cur[N],S,T;
  
  struct edge{
  	int v,nxt,w;
  }e[N<<3];
  
  void add(int u,int v,int w1,int w2){
    e[++tot]={v,head[u],w1},head[u]=tot;
    e[++tot]={u,head[v],w2},head[v]=tot;
  }
  
  bool bfs(){
  	for(int i=S;i<=T;i++) lv[i]=-1,cur[i]=head[i];
  	queue<int> Q;lv[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].v,w=e[i].w;
  	    if(w&&lv[v]==-1){
  	      lv[v]=lv[u]+1,Q.push(v);	
		  if(v==T) return true;
		}
	  }
	}
	return false;
  }
  
  int dfs(int u,int flow){
    if(!flow||u==T) return flow;
    int res=flow;
    for(int i=cur[u];i&&res;i=e[i].nxt){
      cur[u]=i;
      int v=e[i].v,w=e[i].w;
      if(w&&lv[v]==lv[u]+1){
      	int c=dfs(v,min(res,w));
      	res-=c,e[i].w-=c,e[i^1].w+=c;
	  }
	}
	return flow-res;
  }
  
  void dinic(){
    int res=0;
  	while(bfs()) res+=dfs(S,1e9);
//  	cerr<<"res = "<<res<<endl;
    assert(res==2);
  }
}
using namespace MF;

void BFS(){
  for(int i=S;i<=T;i++) lv[i]=-1;
  queue<int> Q;Q.push(S),lv[S]=1;
  while(!Q.empty()){
  	int u=Q.front();Q.pop();
  	for(int i=head[u];i;i=e[i].nxt){
  	  int v=e[i].v,w=e[i].w;
  	  if(w||~lv[v]) continue;
  	  lv[v]=lv[u]+1,Q.push(v);
  	  if(v==T){
//  	  	cerr<<"lv( "<<T<<" ) = "<<lv[T]<<endl;
  	    return;	
	  }
	}
  }
  assert(0);
}

void find(int u){
  if(u==S) return;
  if(u!=T) Ans.pb(u);
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(e[i^1].w||lv[v]!=lv[u]-1) continue;
  	e[i^1].w=1,find(v);
  	break;
  }
}

int main(){
//  freopen("1.in","r",stdin);
  /*2025.1.19 H_W_Y QOJ 4809. Maximum Range 边双 + 网络流*/ 
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m;
  for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,G[u].pb({v,w}),G[v].pb({u,w});
  for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
  for(int i=1;i<=scc;i++) mn[i]=1e9,mx[i]=-1e9;ans=-1e9;
  
  for(int u=1;u<=n;u++)
  	for(auto i:G[u]) if(bl[u]==bl[i.v]) mn[bl[u]]=min(mn[bl[u]],i.w),mx[bl[u]]=max(mx[bl[u]],i.w);
  
  for(int i=1;i<=scc;i++) if(mx[i]-mn[i]>ans) ans=mx[i]-mn[i],id=i;
  
  cout<<ans<<'\n';
  
  vector<int> V(0);
  for(int i=1;i<=n;i++) if(bl[i]==id) V.pb(i);
  
  S=0,T=n+1;
  for(int u:V){
  	for(auto i:G[u]){
  	  int v=i.v,w=i.w;
	  if(bl[u]!=bl[v]||v<u) continue;
	  if(w==mn[id]) add(S,u,1,0),add(S,v,1,0),mn[id]=1e9+1;
	  else if(w==mx[id]) add(u,T,1,0),add(v,T,1,0),mx[id]=-1e9-1;
	  else add(u,v,1,1);
	}
  }
  
  dinic();
  
  BFS(),find(T);
  V=Ans,Ans.clear(),BFS(),find(T);
  for(int i=(int)V.size()-1;i>=0;i--) Ans.pb(V[i]);
  
  cout<<(int)Ans.size()<<'\n';
  for(int i:Ans) cout<<i<<' ';
  cout<<'\n';
  return 0;
}
/*
5 7
1 2 1
1 3 -2
2 3 1
3 4 3
4 5 1
1 5 -1
2 5 2
*/