题意：\(n\) 个点的图，找一个有 \(k\) 个点的的简单环，使其边权和最大。
随机黑白染色，拆成两条颜色不同的不相交链，做 \(300\) 次即可。链的情况是好做的，做完后，预处理 \(f_{x,y}\) 表示 \(x\) 到 \(y\) 的最大距离，枚举两条端点颜色不同的边可以直接合并。
链点数 \(\leq 4\) 都是可以直接暴力枚举的，现在考虑 \(5\) 的情况。预处理 \(h_{x,y}\) 表示 \(x,y\) 间加一个点的最大链长，预处理前三大，剩下再暴力枚举即可。
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
struct IO {
char ibuf[(1 << 20) + 1], *iS, *iT, obuf[(1 << 20) + 1], *oS;
IO() : iS(ibuf), iT(ibuf), oS(obuf) {} ~IO() { fwrite(obuf, 1, oS - obuf, stdout); }
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
inline bool eof (const char &ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == 't' || ch == EOF; }
inline long long read() {
char ch = gh();
long long x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void read (char *s) {
char ch = gh(); int l = 0;
while (eof(ch)) ch = gh();
while (!eof(ch)) s[l++] = ch, ch = gh();
}
inline void read (double &x) {
char ch = gh(); bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
if (ch != '.') return t && (x = -x), void(); ch = gh();
for (double cf = 0.1; '0' <= ch && ch <= '9'; ch = gh(), cf *= 0.1) x += cf * (ch ^ 48);
t && (x = -x);
}
inline void pc (char ch) {
#ifdef ONLINE_JUDGE
if (oS == obuf + (1 << 20) + 1) fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
*oS++ = ch;
#else
putchar(ch);
#endif
}
template<typename _Tp>
inline void write (_Tp x) {
static char stk[64], *tp = stk;
if (x < 0) x = ~(x - 1), pc('-');
do *tp++ = x % 10, x /= 10;
while (x);
while (tp != stk) pc((*--tp) | 48);
}
inline void write (char *s) {
int n = strlen(s);
for (int i = 0; i < n; i++) pc(s[i]);
}
} io;
inline long long read () { return io.read(); }
template<typename Tp>
inline void read (Tp &x) { io.read(x); }
template<typename _Tp>
inline void write (_Tp x) { io.write(x); }
}
using namespace FastIO;
#define int long long
const int maxn=305,inf=1e18;
int n,m,k;
vector< tuple<int,int,int> > G[maxn];
bool col[maxn];
int f[6][maxn][maxn],up[maxn],vp[maxn],wp[maxn],h[maxn][maxn][3],idh[maxn][maxn][3];
mt19937 rnd(231232134);
void init1()
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[1][i][j]=-inf;
for(int i=1;i<=n;i++)f[1][i][i]=0;
}
void init2()
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[2][i][j]=-inf;
for(int i=1;i<=m;i++)
if(col[up[i]]==col[vp[i]])f[2][up[i]][vp[i]]=f[2][vp[i]][up[i]]=max(f[2][up[i]][vp[i]],wp[i]);
}
inline void init3()
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[3][i][j]=-inf;
for(int i=1;i<=n;i++)
for(auto [j,w1,id1]:G[i])
for(auto [k,w2,id2]:G[i])
if(col[i]==col[j]&&col[i]==col[k]&&j!=k)
f[3][k][j]=f[3][j][k]=max(f[3][j][k],w1+w2);
}
inline void init4()
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[4][i][j]=-inf;
for(int i=1;i<=m;i++)
{
if(col[up[i]]!=col[vp[i]])continue;
for(auto [j,w1,id1]:G[up[i]])
for(auto [k,w2,id2]:G[vp[i]])
if(col[up[i]]==col[j]&&col[vp[i]]==col[k]&&up[i]!=k&&vp[i]!=j&&k!=j)
f[4][j][k]=f[4][k][j]=max(f[4][j][k],w1+w2+wp[i]);
}
}
inline void upd(int v,int id,int i,int j)
{for(int t=0;t<3;t++)if(v>h[i][j][t]){swap(v,h[i][j][t]);swap(id,idh[i][j][t]);}}
inline int findminsec(int idn1,int idn2,int i,int j)
{for(int t=0;t<3;t++)if(idn1!=idh[i][j][t]&&idn2!=idh[i][j][t])return h[i][j][t];return -inf;}
inline void init5()
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[5][i][j]=h[i][j][0]=h[i][j][1]=h[i][j][2]=-inf;
for(int i=1;i<=n;i++)
for(auto [j,w1,id1]:G[i])
for(auto [k,w2,id2]:G[i])
if(col[i]==col[j]&&col[i]==col[k]&&j!=k)
{
upd(w1+w2,i,j,k);
upd(w1+w2,i,k,j);
}
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
{
if(col[up[i]]!=col[vp[i]]||col[up[i]]!=col[up[j]]||col[up[i]]!=col[vp[j]]||col[up[j]]!=col[vp[j]]||up[i]==up[j]||up[i]==vp[j]||vp[i]==up[j]||vp[i]==vp[j])continue;
f[5][up[i]][vp[j]]=max(f[5][up[i]][vp[j]],wp[i]+wp[j]+findminsec(up[i],vp[j],vp[i],up[j]));
f[5][up[i]][up[j]]=max(f[5][up[i]][up[j]],wp[i]+wp[j]+findminsec(up[i],up[j],vp[i],vp[j]));
f[5][vp[i]][vp[j]]=max(f[5][vp[i]][vp[j]],wp[i]+wp[j]+findminsec(vp[i],vp[j],up[i],up[j]));
f[5][vp[i]][up[j]]=max(f[5][vp[i]][up[j]],wp[i]+wp[j]+findminsec(vp[i],up[j],up[i],vp[j]));
}
}
signed main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++)
up[i]=read(),vp[i]=read(),wp[i]=read();
for(int i=1;i<=m;i++)
{
G[up[i]].push_back({vp[i],wp[i],i});
G[vp[i]].push_back({up[i],wp[i],i});
}
int t1=k/2,t2=k-t1,ans=-inf;
if(k==3)
{
init2();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(j!=up[i]&&j!=vp[i])
ans=max(ans,wp[i]+f[2][up[i]][j]+f[2][vp[i]][j]);
}
else
for(int sr=1;sr<=1000;sr++)
{
for(int i=1;i<=n;i++)col[i]=rnd()%2;
if(t1==1||t2==1)init1();
if(t1==2||t2==2)init2();
if(t1==3||t2==3)init3();
if(t1==4||t2==4)init4();
if(t1==5||t2==5)init5();
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
{
if(up[i]!=up[j]&&up[i]!=vp[j]&&vp[i]!=up[j]&&vp[i]!=vp[j])
{
if(col[up[i]]==0&&col[vp[i]]==1&&col[up[j]]==0&&col[vp[j]]==1)
ans=max(ans,f[t1][up[i]][up[j]]+f[t2][vp[i]][vp[j]]+wp[i]+wp[j]);
if(col[up[i]]==0&&col[vp[i]]==1&&col[vp[j]]==0&&col[up[j]]==1)
ans=max(ans,f[t1][up[i]][vp[j]]+f[t2][vp[i]][up[j]]+wp[i]+wp[j]);
if(col[vp[i]]==0&&col[up[i]]==1&&col[up[j]]==0&&col[vp[j]]==1)
ans=max(ans,f[t1][vp[i]][up[j]]+f[t2][up[i]][vp[j]]+wp[i]+wp[j]);
if(col[vp[i]]==0&&col[up[i]]==1&&col[vp[j]]==0&&col[up[j]]==1)
ans=max(ans,f[t1][vp[i]][vp[j]]+f[t2][up[i]][up[j]]+wp[i]+wp[j]);
}
}
}
if(ans>0)printf("%lld\n",ans);
else puts("impossible");
}