#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
using i64 = long long;
using namespace std;

const int N = 3e2 + 1;
int n, m, k;
vector<pair<int, int>> adj[N];
int ans, dp[N][1 << 10], c[N];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

	cin >> n >> m >> k;
	for (int i = 1, u, v, w; i <= m; i++)
	{
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	
	ans = -2e9;
	mt19937 rnd(time(0));
	clock_t cur = clock();
	int all = (1 << k) - 1;
	do
	{
		for (int i = 1; i <= n; i++)
			c[i] = rnd() % k;
		for (int i = 1; i <= n; i++)
		{
			memset(dp, -0x7f, sizeof(dp));
			dp[i][0] = 0;
			for (int s = 0; s < all; s++)
			{
				for (int j = 1; j <= n; j++)
				{
					if (dp[j][s] < 0) continue;
					for (auto [to, w] : adj[j])
						dp[to][s ^ (1 << c[to])] = max(dp[j][s] + w, dp[to][s ^ (1 << c[to])]);
				}
			}
			ans = max(ans, dp[i][all]);
		}
	} while (clock() - cur <= 3000);
	if (ans < 0) cout << "impossible\n";
	else cout << ans << '\n';
}