#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define pii pair<int,int> #define p1(x) (x).first #define p2(x) (x).second struct edge{ int v,w,nxt; }E[4030]; int eid=1; int n,m; int d[510],hd[510],rd[510]; inline void clr(){ for(int i=2;i<=eid;i+=2) E[i].w=E[i^1].w=(E[i].w+E[i^1].w)/2; } inline void add(int u,int v,int w){ ++eid; E[eid]={v,w,hd[u]}; hd[u]=eid; ++eid; E[eid]={u,w,hd[v]}; hd[v]=eid; } inline int bfs(int S,int T){ memset(d,-1,sizeof(d)); d[S]=0; queue<int>q; q.push(S); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=hd[u];i;i=E[i].nxt){ int v=E[i].v,w=E[i].w; if(w&&d[v]==-1){ // cout<<u<<" "<<v<<" "<<i<<" "<<w<<endl; d[v]=d[u]+1; q.push(v); } } } // cout<<endl; return d[T]!=-1; } inline int dfs(int u,int T,int fl){ if(u==T)return fl; int res=0; for(int i=rd[u];i;i=E[i].nxt){ int v=E[i].v,w=E[i].w; if(w&&d[v]==d[u]+1){ int t=dfs(v,T,min(fl,w)); // cout<<u<<"x"<<v<<"x"<<i<<"x"<<w<<"x"<<t<<endl; E[i].w-=t; fl-=t; res+=t; E[i^1].w+=t; } if(!fl)break; rd[u]=E[i].nxt; } return res; } inline int dinic(int S,int T){ int res=0; clr(); // int cnt=0; while(bfs(S,T)){ // for(int i=1;i<=n;i++) // cout<<d[i]<<" "; // cout<<endl; // cout.flush(); // cnt++; // if(cnt==4)return 0; memcpy(rd,hd,sizeof(hd)); res+=dfs(S,T,1e8); } return res; } bool vis[510]; inline void dfsS(int S){ memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(S); vis[S]=1; while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int i=hd[u];i;i=E[i].nxt){ int v=E[i].v,w=E[i].w; if(w&&!vis[v]){ vis[v]=1; Q.push(v); } } } } struct EDGE{ int u,v,w; }; vector<EDGE>ED; inline void go_hu(vector<int>P){ if(P.size()<=1)return ; vector<int>X,Y; int S=P[0],T=P[1]; int res=dinic(S,T); ED.push_back((EDGE){S,T,res}); // cout<<S<<" "<<T<<" "<<res<<endl; dfsS(S); for(int x:P) if(vis[x])X.push_back(x); else Y.push_back(x); go_hu(X); go_hu(Y); } int siz[1030]; int lc[1030],rc[1030]; int w[1030]; int f[1003]; vector<int>ST[1003]; inline int ff(int x){ return f[x]==x?x:f[x]=ff(f[x]); } int cnt=0; inline void merge(int x,int y,int val){ x=ff(x),y=ff(y); if(x==y)return ; if(siz[x]<siz[y])swap(x,y); cnt++; f[cnt]=cnt; f[x]=f[y]=cnt; siz[cnt]=siz[x]+siz[y]; w[cnt]=val; lc[cnt]=x,rc[cnt]=y; for(int s:ST[x]) ST[cnt].push_back(s); for(int s:ST[y]) ST[cnt].push_back(s); // cout<<x<<" "<<y<<" "<<cnt<<endl; // cout.flush(); } long long res=0; int g[510]; inline priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> calc(int x){ int t=siz[rc[x]]; priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>res; // cout<<x<<" "<<lc[x]<<" "<<rc[x]<<" "<<siz[x]<<endl; // cout.flush(); if(x==0)exit(0); if(siz[x]==1){ res.push({w[x],{x,x}}); return res; } auto A=calc(lc[x]); auto B=calc(rc[x]); // cout<<A.size()<<" "<<B.size()<<endl; // cout.flush(); // assert(!A.empty()); // assert(!B.empty()); res.push({w[x],{p1(p2(A.top())),p2(p2(B.top()))}}); res.push({w[x],{p1(p2(B.top())),p2(p2(A.top()))}}); A.pop(),B.pop(); while(!A.empty()) res.push(A.top()),A.pop(); while(!B.empty()) res.push(B.top()),B.pop(); return res; } inline bool cmp(EDGE A,EDGE B){ return A.w>B.w; } inline void opt(int x){ if(vis[x])return ; vis[x]=1; cout<<x<<" "; opt(g[x]); } signed main(){ // freopen("maxflow.in","r",stdin); // freopen("maxflow.out","w",stdout); // freopen("sample.in","r",stdin); // freopen("sample.out","w",stdout); ios::sync_with_stdio(0); cin>>n>>m; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; add(u,v,w); } // cout<<dinic(1,2)<<" "<<dinic(1,3)<<" "<<dinic(2,3)<<endl;; vector<int>ALL; for(int i=1;i<=n;i++) ALL.push_back(i),f[i]=i,siz[i]=1,ST[i].push_back(i); go_hu(ALL); cnt=n; sort(ED.begin(),ED.end(),cmp); for(auto e:ED) merge(e.u,e.v,e.w); auto q=calc(ff(1)); while(!q.empty()) res+=p1(q.top()),g[p1(p2(q.top()))]=p2(p2(q.top())),q.pop(); cout<<res<<endl; memset(vis,0,sizeof(vis)); // return 0; opt(1); cout<<endl; cout.flush(); return 0; } /* 3 3 1 2 1 2 3 1 1 3 2 5 10 1 2 9 1 3 3 1 4 10 1 5 2 2 3 5 2 4 4 2 5 2 3 4 8 3 5 5 4 5 8 */