// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int K;
vector< pair<int, int> > monsters;
vector< vector< pair<int, int> > > cycles;
vector<int> checked;
vector< pair<int, int> > G[2010];

int dpn[2010][2][2], dpc[2010][2][2];

void make_vec(int cur) {
    queue<int> que;
    que.push(cur);
    monsters.emplace_back(cur, 0);
    while(que.size()) {
        int v = que.front(); que.pop();
        for(auto e : G[v]) {
            int to, cost; tie(to, cost) = e;
            if(checked[to]) continue;
            if(cost == 0) cost = -INF;
            checked[to] = true;
            monsters.emplace_back(to, cost);
            que.push(to);
        }
    }
}

void make_cycle(int cur) {
    queue<int> que;
    que.push(cur);
    vector< pair<int, int> > cycle;
    cycle.emplace_back(cur, 0);
    while(que.size()) {
        int v = que.front(); que.pop();
        bool first_v = true;
        
        for(auto e : G[v]) {
            int to, cost; tie(to, cost) = e;
            if(cost == 0) cost = -INF;
            if(checked[to]) continue;
            if(!first_v) {
                cycle[0].second = cost;
                continue;
            }
            first_v = false;
            checked[to] = true;
            cycle.emplace_back(to, cost);
            que.push(to);
        }
    }
    cycles.emplace_back(cycle);
}

vector<int> solve_vec() {
    int N = monsters.size();
    fill(dpc[0][0], dpc[K+1][0], -INF);
    fill(dpn[0][0], dpn[K+1][0], -INF);
    dpc[0][0][0] = 0;

    // i 匹目まで見た、j 匹とった、直前は取った？
    for(int i=0; i<N; i++) {
        int id, cost; tie(id, cost) = monsters[i];
        for(int j=0; j<=K; j++) {
            // 取る (超仲が悪いとできない)
            if(cost != -INF) {
                if(j+1 <= K and dpc[j][1][0] > -INF) chmax(dpn[j+1][1][0], dpc[j][1][0] + cost);
            }
            if(j+1 <= K) chmax(dpn[j+1][1][0], dpc[j][0][0]);
            
            // 取らない (前をどう取ったか関係ない)
            chmax(dpn[j][0][0], max(dpc[j][0][0], dpc[j][1][0]));
        }
        fill(dpc[0][0], dpc[K+1][0], -INF);
        swap(dpn, dpc);
    }

    int sz = min(N, K) + 1;
    vector<int> res(sz, -INF);
    for(int i=0; i<sz; i++) {
        res[i] = max(dpc[i][0][0], dpc[i][1][0]);
        // fprintf(stderr, "res[%lld] = %lld\n", i, res[i]);
    }
    return res;
}

vector<int> solve_cycle(vector< pair<int, int> > cycle) {
    int N = cycle.size();
    fill(dpc[0][0], dpc[K+1][0], -INF);
    fill(dpn[0][0], dpn[K+1][0], -INF);
    dpc[0][0][0] = 0;

    for(int i=0; i<N; i++) {
        int id, cost; tie(id, cost) = cycle[i];
        int acost = (i == N-1 ? cycle[0].second : 0);
        // fprintf(stderr, "i = %lld, acost = %lld\n", i, acost);
        for(int j=0; j<=K; j++) {
            // 取る (超仲が悪いとできない)
            // N - 1 番目なら先頭ともチェックする
            if(i == 0) cost = 0;
            bool a1 = (cost == -INF);
            bool a2 = (i == N-1 and cycle[0].second == -INF);
            if(j+1 <= K) {
                // 前とも次とも仲悪くない
                if(!a1 and !a2) {
                    if(dpc[j][1][1] > -INF) chmax(dpn[j+1][1][1], dpc[j][1][1] + cost + acost);
                    if(dpc[j][1][0] > -INF) chmax(dpn[j+1][1][i==0], dpc[j][1][0] + cost);
                    if(dpc[j][0][1] > -INF) chmax(dpn[j+1][1][1], dpc[j][0][1] + acost);
                    if(dpc[j][0][0] > -INF) chmax(dpn[j+1][1][i==0], dpc[j][0][0]);
                }
                // 前と仲悪くて次とは仲悪くない
                // 前は選べない
                else if(a1) {
                    if(dpc[j][0][1] > -INF) chmax(dpn[j+1][1][1], dpc[j][0][1] + acost);
                    if(dpc[j][0][0] > -INF) chmax(dpn[j+1][1][i==0], dpc[j][0][0]);
                }
                // 前と仲悪くなくて次とは仲悪い
                // 3 次元目が 1 のやつは選べない
                else if(a2) {
                    chmax(dpn[j+1][1][i==0], dpc[j][0][0]);
                    if(dpc[j][1][0] > -INF) chmax(dpn[j+1][1][i==0], dpc[j][1][0] + cost);
                }
                // どっちとも仲悪い
                // 前も後ろも選べない
                else if(a1 and a2) {
                    // 最初も前も選んでない
                    chmax(dpn[j+1][1][i==0], dpc[j][0][0]);
                }
            }

            // 取らない (いかなる場合でも可能、最初だけ注意)
            chmax(dpn[j][0][0], max(dpc[j][0][0], dpc[j][1][0]));
            chmax(dpn[j][0][1], max(dpc[j][0][1], dpc[j][1][1]));
        }
        fill(dpc[0][0], dpc[K+1][0], -INF);
        swap(dpn, dpc);
    }

    int sz = min(N, K) + 1;
    vector<int> res(sz, -INF);
    for(int i=0; i<sz; i++) {
        int ma = max({dpc[i][0][0], dpc[i][0][1], dpc[i][1][0], dpc[i][1][1]});
        // fprintf(stderr, "cycle: res[%lld] = %lld\n", i, ma);
        res[i] = ma;
    }
    return res;
}

vector<int> merge(vector<int> A, vector<int> B) {
    int N = A.size(), M = B.size();
    vector<int> res(N + M - 1, -INF);
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(A[i] == -INF or B[j] == -INF) continue;
            chmax(res[i+j], A[i] + B[j]);
        }
    }
    return res;
}

signed main() {
    int N, M; cin >> N >> M >> K;
    checked.resize(N);
    for(int i=0; i<M; i++) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }

    for(int i=0; i<N; i++) {
        if(checked[i]) continue;
        if(G[i].size() > 1) continue;
        checked[i] = true;
        make_vec(i);
    }

    for(int i=0; i<N; i++) {
        if(checked[i]) continue;
        checked[i] = true;
        make_cycle(i);
    }

    for(auto e : monsters) {
        int a, b; tie(a, b) = e;
        // fprintf(stderr, "%lld %lld\n", a, b);
    }

    for(auto c : cycles) {
        // fprintf(stderr, "cycle:");
        for(auto e : c) {
            int a, b; tie(a, b) = e;
            // fprintf(stderr, " (%lld, %lld)", a, b);
        }
        // fprintf(stderr, "\n");
    }

    auto vec = solve_vec();
    for(auto c : cycles) {
        auto vec_c = solve_cycle(c);
        vec = merge(vec, vec_c);
    }

    if(vec.size() < K + 1 or vec[K] == -INF) cout << "Impossible" << endl;
    else cout << vec[K] << endl;
    return 0;
}



Measured memory_bytes: 3568