package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type OrigEdge struct {
	to   int
	cost int
}

type Edge struct {
	w    uint32
	cost int
}

type Branch struct {
	add       int
	childMask uint32
	child     *State
	base      bool
}

type Item struct {
	val int
	br  int
	pos int
}

type State struct {
	i        int
	mask     uint32
	ready    bool
	vals     []int
	branches []Branch
	heap     []Item
}

type PairItem struct {
	sum int
	i   int
	j   int
}

var curMen [][]Edge
var curM int
var curLimit int
var memo []map[uint32]*State

func pushItem(h *[]Item, x Item) {
	a := *h
	a = append(a, x)
	i := len(a) - 1
	for i > 0 {
		p := (i - 1) >> 1
		if a[p].val <= x.val {
			break
		}
		a[i] = a[p]
		i = p
	}
	a[i] = x
	*h = a
}

func popItem(h *[]Item) Item {
	a := *h
	res := a[0]
	x := a[len(a)-1]
	a = a[:len(a)-1]
	if len(a) > 0 {
		i := 0
		for {
			l := i*2 + 1
			if l >= len(a) {
				break
			}
			c := l
			r := l + 1
			if r < len(a) && a[r].val < a[l].val {
				c = r
			}
			if a[c].val >= x.val {
				break
			}
			a[i] = a[c]
			i = c
		}
		a[i] = x
	}
	*h = a
	return res
}

func pushPair(h *[]PairItem, x PairItem) {
	a := *h
	a = append(a, x)
	i := len(a) - 1
	for i > 0 {
		p := (i - 1) >> 1
		if a[p].sum <= x.sum {
			break
		}
		a[i] = a[p]
		i = p
	}
	a[i] = x
	*h = a
}

func pairSiftDown(h []PairItem, i int) {
	n := len(h)
	x := h[i]
	for {
		l := i*2 + 1
		if l >= n {
			break
		}
		c := l
		r := l + 1
		if r < n && h[r].sum < h[l].sum {
			c = r
		}
		if h[c].sum >= x.sum {
			break
		}
		h[i] = h[c]
		i = c
	}
	h[i] = x
}

func pairHeapify(h []PairItem) {
	for i := len(h)/2 - 1; i >= 0; i-- {
		pairSiftDown(h, i)
	}
}

func popPair(h *[]PairItem) PairItem {
	a := *h
	res := a[0]
	x := a[len(a)-1]
	a = a[:len(a)-1]
	if len(a) > 0 {
		a[0] = x
		pairSiftDown(a, 0)
	}
	*h = a
	return res
}

func getState(i int, mask uint32) *State {
	if st, ok := memo[i][mask]; ok {
		return st
	}
	st := &State{i: i, mask: mask}
	memo[i][mask] = st
	return st
}

func (s *State) prepare() {
	if s.ready {
		return
	}
	s.ready = true
	nextBase := s.i+1 == curM
	mask := s.mask
	s.branches = make([]Branch, 0, 1+len(curMen[s.i]))
	s.heap = make([]Item, 0, 1+len(curMen[s.i]))
	s.branches = append(s.branches, Branch{add: 0, childMask: mask, base: nextBase})
	pushItem(&s.heap, Item{val: 0, br: 0, pos: 0})
	for _, e := range curMen[s.i] {
		bit := uint32(1) << e.w
		if mask&bit == 0 {
			bi := len(s.branches)
			s.branches = append(s.branches, Branch{add: e.cost, childMask: mask | bit, base: nextBase})
			pushItem(&s.heap, Item{val: e.cost, br: bi, pos: 0})
		}
	}
}

func (s *State) get(idx int) (int, bool) {
	if idx < len(s.vals) {
		return s.vals[idx], true
	}
	if idx >= curLimit {
		return 0, false
	}
	s.prepare()
	for len(s.vals) <= idx {
		if len(s.heap) == 0 {
			return 0, false
		}
		it := popItem(&s.heap)
		s.vals = append(s.vals, it.val)
		b := &s.branches[it.br]
		if !b.base {
			if b.child == nil {
				b.child = getState(s.i+1, b.childMask)
			}
			if v, ok := b.child.get(it.pos + 1); ok {
				pushItem(&s.heap, Item{val: b.add + v, br: it.br, pos: it.pos + 1})
			}
		}
	}
	return s.vals[idx], true
}

func sortProc(proc [][]Edge) {
	for i := range proc {
		lst := proc[i]
		sort.Slice(lst, func(a, b int) bool {
			if lst[a].cost != lst[b].cost {
				return lst[a].cost < lst[b].cost
			}
			return lst[a].w < lst[b].w
		})
	}
	sort.Slice(proc, func(i, j int) bool {
		if len(proc[i]) != len(proc[j]) {
			return len(proc[i]) < len(proc[j])
		}
		if len(proc[i]) == 0 {
			return false
		}
		if proc[i][0].cost != proc[j][0].cost {
			return proc[i][0].cost < proc[j][0].cost
		}
		return proc[i][0].w < proc[j][0].w
	})
}

func computeList(proc [][]Edge, limit int) []int {
	if len(proc) == 0 {
		return []int{0}
	}
	curMen = proc
	curM = len(proc)
	curLimit = limit
	memo = make([]map[uint32]*State, curM)
	for i := 0; i < curM; i++ {
		memo[i] = make(map[uint32]*State)
	}
	root := getState(0, 0)
	res := make([]int, 0, limit)
	for i := 0; i < limit; i++ {
		v, ok := root.get(i)
		if !ok {
			break
		}
		res = append(res, v)
	}
	return res
}

func mergeLists(a, b []int, limit int) []int {
	if len(a) == 0 || len(b) == 0 {
		return nil
	}
	if len(a) > len(b) {
		a, b = b, a
	}
	if len(a) > limit {
		a = a[:limit]
	}
	h := make([]PairItem, len(a))
	for i := 0; i < len(a); i++ {
		h[i] = PairItem{sum: a[i] + b[0], i: i, j: 0}
	}
	pairHeapify(h)
	res := make([]int, 0, limit)
	for len(res) < limit && len(h) > 0 {
		it := popPair(&h)
		res = append(res, it.sum)
		if it.j+1 < len(b) {
			pushPair(&h, PairItem{sum: a[it.i] + b[it.j+1], i: it.i, j: it.j + 1})
		}
	}
	return res
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, k, t int
	fmt.Fscan(in, &n, &k, &t)
	if t == 1 {
		fmt.Fprintln(out, 0)
		return
	}

	menOrig := make([][]OrigEdge, n)
	womenOrig := make([][]OrigEdge, n)
	graph := make([][]int, 2*n)

	for i := 0; i < k; i++ {
		var h, w, r int
		fmt.Fscan(in, &h, &w, &r)
		h--
		w--
		menOrig[h] = append(menOrig[h], OrigEdge{to: w, cost: r})
		womenOrig[w] = append(womenOrig[w], OrigEdge{to: h, cost: r})
		graph[h] = append(graph[h], n+w)
		graph[n+w] = append(graph[n+w], h)
	}

	visited := make([]bool, 2*n)
	vals := []int{0}

	for s := 0; s < 2*n; s++ {
		if visited[s] || len(graph[s]) == 0 {
			continue
		}
		q := []int{s}
		visited[s] = true
		compMen := make([]int, 0)
		compWomen := make([]int, 0)

		for qi := 0; qi < len(q); qi++ {
			v := q[qi]
			if v < n {
				compMen = append(compMen, v)
			} else {
				compWomen = append(compWomen, v-n)
			}
			for _, u := range graph[v] {
				if !visited[u] {
					visited[u] = true
					q = append(q, u)
				}
			}
		}

		var proc [][]Edge
		if len(compWomen) <= len(compMen) {
			wmap := make([]int, n)
			for i := range wmap {
				wmap[i] = -1
			}
			for i, w := range compWomen {
				wmap[w] = i
			}
			proc = make([][]Edge, len(compMen))
			for i, m := range compMen {
				lst := make([]Edge, len(menOrig[m]))
				for j, e := range menOrig[m] {
					lst[j] = Edge{w: uint32(wmap[e.to]), cost: e.cost}
				}
				proc[i] = lst
			}
		} else {
			mmap := make([]int, n)
			for i := range mmap {
				mmap[i] = -1
			}
			for i, m := range compMen {
				mmap[m] = i
			}
			proc = make([][]Edge, len(compWomen))
			for i, w := range compWomen {
				lst := make([]Edge, len(womenOrig[w]))
				for j, e := range womenOrig[w] {
					lst[j] = Edge{w: uint32(mmap[e.to]), cost: e.cost}
				}
				proc[i] = lst
			}
		}

		sortProc(proc)
		comp := computeList(proc, t)
		vals = mergeLists(vals, comp, t)
	}

	fmt.Fprintln(out, vals[t-1])
}