#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt,__func__,__LINE__,##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=1e5+5,inf=1e9+7;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n,m;
vector<tuple<int,int,int> >G[N];
tuple<int,int,int>E[N];
int dfn[N],low[N],cdfn,stk[N],tp;
int bel[N],bcc,Mx[N],Mn[N],Mnid[N],Mxid[N];
void tarjan(int u,int fa){
  dfn[u]=low[u]=++cdfn;stk[++tp]=u;
  for(auto [v,_,__] within G[u]) if(v!=fa){
    if(!dfn[v]) tarjan(v,u),low[u]=min(low[u],low[v]);
    else low[u]=min(low[u],dfn[v]);
  }if(low[u]==dfn[u]){
    int y;++bcc;Mn[bcc]=inf;Mx[bcc]=-inf;
    while(y=stk[tp--]){bel[y]=bcc;if(y==u) break;}
  }
}
int h[N],dep[N],cur[N],ce=1,s,t;
struct Edge{int v,w,nxt;}e[N<<1];
void addedge(int u,int v){
  debug("%d %d\n",u,v);
  e[++ce]={v,1,h[u]};h[u]=ce;e[++ce]={u,1,h[v]};h[v]=ce;}
vector<int>Ans;
bool bfs(){
  static queue<int>q;while(!q.empty()) q.pop();
  For(i,1,t) dep[i]=0,cur[i]=h[i];dep[s]=1;q.emplace(s);
  while(!q.empty()){
    int u=q.front();q.pop();
    for(int i=h[u];i;i=e[i].nxt) if(e[i].w&&!dep[e[i].v]){
      int v=e[i].v;dep[v]=dep[u]+1;
      if(v==t) return 1;q.emplace(v);
    }
  }return 0;
}
int dfs(int u,int flow){
  if(u==t) return flow;int rec=0;
  for(int&i=cur[u];i;i=e[i].nxt){
    int v=e[i].v,w=e[i].w;
    if(!w||dep[v]!=dep[u]+1) continue;
    int ret=dfs(v,min(flow-rec,e[i].w));
    rec+=ret;e[i].w-=ret;e[i^1].w+=ret;
    if(rec==flow) return flow;
  }return rec;
}
void Dinic(int S,int T){s=S;t=T;while(bfs()) dfs(s,inf);}
void print(int u,int v){
  // debug("%d %d\n",u,v);
  if(u<=n) Ans.emplace_back(u);if(u==v) return;
  for(int i=h[u];i;i=e[i].nxt) if(!e[i].w){e[i].w=inf;print(e[i].v,v);return;}
}
signed LJY(){
  n=read();m=read();
  For(i,1,m){
    int u=read(),v=read(),w=read();E[i]={u,v,w};
    G[u].emplace_back(v,w,i);
    G[v].emplace_back(u,w,i);
  }For(i,1,n) if(!dfn[i]) tarjan(i,0);
  For(i,1,n) for(auto [v,w,id] within G[i]) if(bel[i]==bel[v]){
    if(Mn[bel[i]]>w) Mn[bel[i]]=w,Mnid[bel[i]]=id;
    if(Mx[bel[i]]<w) Mx[bel[i]]=w,Mxid[bel[i]]=id;
  }int ans=0,id=0;
  For(i,1,bcc) if(Mx[i]-Mn[i]>ans) ans=Mx[i]-Mn[i],id=i;
  printf("%d\n",ans);int S=n+1,T=n+2;
  auto [u,v,w]=E[Mnid[id]];addedge(S,u);addedge(S,v);
  tie(u,v,w)=E[Mxid[id]];addedge(u,T);addedge(v,T);
  For(i,1,n) if(bel[i]==id) for(auto [v,w,Id] within G[i])
    if(i<v&&bel[v]==id&&Id!=Mnid[id]&&Id!=Mxid[id]) addedge(i,v);
  Dinic(S,T);print(S,T);reverse(Ans.begin(),Ans.end());print(S,T);
  printf("%d\n",Ans.size());for(int x within Ans) printf("%d ",x);
  return 0;
}