#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,dp[(1<<18)+5][19],pre[(1<<18)+5][19],w[20][20],Log2[20]; vector<pi>v[105]; vector<int>F[105]; struct Graph { vector<pi>v[4005]; int w[4005],dis[4005]; int S,T; int ct=1; void clear(){ up(i,1,100)v[i].clear(); memset(w,0,sizeof(w)),memset(dis,0,sizeof(dis)); ct=1; } void ins(int x,int y,int ww){ v[x].p_b(m_p(y,++ct)); w[ct]=ww; v[y].p_b(m_p(x,++ct)); }bool bfs(){ memset(dis,-1,sizeof(dis)); dis[S]=0;queue<int>q; q.push(S);while(!q.empty()){ int x=q.front();q.pop(); for(auto it:v[x]){ if(dis[it.p1]!=-1)continue; if(!w[it.p2])continue; dis[it.p1]=dis[x]+1; q.push(it.p1); } }return (dis[T]!=-1); }ll dfs(int u,int flow){ if(u==T)return flow; int res=0; for(auto it:v[u]){ if(!w[it.p2])continue; if(dis[it.p1]!=dis[u]+1)continue; ll tmp=dfs(it.p1,min(flow,w[it.p2])); flow-=tmp; w[it.p2]-=tmp,w[it.p2^1]+=tmp; res+=tmp; if(!flow)break; }return res; }ll dinic(){ ll res=0; while(bfs()){ res+=dfs(S,1e9); }return res; } }T; int cal(int x,int y){ T.clear(); up(i,1,n){ for(auto it:v[i])T.ins(i,it.p1,it.p2); }T.S=x,T.T=y; return T.dinic(); } int get(int u){ memset(dp,128,sizeof(dp)); dp[(1<<(u-1))][u-1]=0; up(i,1,(1<<n)-1){ int x=i; vector<int>qwq; while(x){ int t=Log2[x]; qwq.p_b(t),x-=(1<<t); }for(auto it:qwq){ for(auto jt:qwq){ if(jt==it)continue; if(dp[i^(1<<it)][jt]+w[jt+1][it+1]>dp[i][it]){ dp[i][it]=dp[i^(1<<it)][jt]+w[jt+1][it+1]; pre[i][it]=jt; } } } }ll res=0;int id=0; up(i,0,n-1)if(dp[(1<<n)-1][i]+w[i+1][u]>res){ res=dp[(1<<n)-1][i]+w[i+1][u];id=i; }int S=(1<<n)-1; while(S!=(1<<(u-1))){ F[u].p_b(id+1); int ts=S;S^=(1<<id); id=pre[ts][id]; } F[u].p_b(u); reverse(F[u].begin(),F[u].end()); return res; } void slv(){ n=read(),m=read(); up(i,2,(1<<n))Log2[i]=Log2[i>>1]+1; up(i,1,m){ int x=read(),y=read(),w=read(); v[x].p_b(m_p(y,w)),v[y].p_b(m_p(x,w)); } up(i,1,n)up(j,1,n)if(i!=j)w[i][j]=cal(i,j); // up(i,1,n)up(j,1,n)if(i!=j)cout<<i<<' '<<j<<' '<<w[i][j]<<'\n'; ll res=0;int id=0; up(i,1,n){ int s=get(i); if(s>res)res=s,id=i; } printf("%lld\n",res); for(int x:F[id])printf("%d ",x);printf("\n"); }int main(){ // freopen("maxflow.in","r",stdin); // freopen("maxflow.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }