#include <bits/stdc++.h> using namespace std; #define int long long #define all(v) v.begin(), v.end() const int inf = 1e18; signed main() { int n,k; cin>>n>>k; vector<int> v; for (int i=0;i<n;i++) if (i<n-k) v.push_back(0); else v.push_back(1); vector<vector<int>> dis(n,vector<int>(n,inf)); for (int i=1;i<n;i++) { int u,v,w; cin>>u>>v>>w; u--,v--; dis[u][v]=dis[v][u]=w; dis[u][u]=dis[v][v]=0; } for (int i=0;i<k;i++) for (int i=0;i<n;i++) for(int j=0;j<n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); int ans=1e18; vector<int> p; do { int mx=0; for (int i=0;i<n;i++) { int d=inf; for (int j=0;j<n;j++) if (v[j]) d=min(d,dis[i][j]); mx=max(mx,d); } if (mx<ans) ans=mx, p=v; }while (next_permutation(all(v))); cout<<ans<<endl; for (int i:p) cout<<i+1<<' '; cout<<endl; return 0; }