For a given weighted directed graph G(V, E), find the distance of the shortest route that meets the following criteria:

* It is a closed cycle where it ends at the same point it starts.
* It visits each vertex exactly once.

Constraints

* 2 ≤ |V| ≤ 15
* 0 ≤ di ≤ 1,000
* There are no multiedge

Input


|V| |E|
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1


|V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target vertices of i-th edge (directed) and di represents the distance between si and ti (the i-th edge).

Output

Print the shortest distance in a line. If there is no solution, print -1.

Examples

Input

4 6
0 1 2
1 2 3
1 3 9
2 0 1
2 3 6
3 2 4


Output

16


Input

3 3
0 1 1
1 2 1
0 2 1


Output

-1
package main

import (
	"container/heap"
	"fmt"
)

type Scanner struct{}

func (sc Scanner) Next() (s string) {
	fmt.Scan(&s)
	return
}

func (sc Scanner) NextInt() (i int) {
	fmt.Scan(&i)
	return
}

type MinCostStatus struct {
	Visited   int
	PrevPoint int
}

type Status struct {
	MinCostStatus
	Cost int
}

type PriorityQueueStatus []*Status

func (pq PriorityQueueStatus) Len() int {
	return len(pq)
}

func (pq PriorityQueueStatus) Less(i, j int) bool {
	return pq[i].Cost < pq[j].Cost
}

func (pq PriorityQueueStatus) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueueStatus) Push(data interface{}) {
	*pq = append(*pq, data.(*Status))
}

func (pq *PriorityQueueStatus) Pop() interface{} {
	l := len(*pq)
	item := (*pq)[l-1]
	*pq = (*pq)[0 : l-1]
	return item
}

func main() {
	var sc Scanner
	v, e := sc.NextInt(), sc.NextInt()
	m := make([]map[int]int, v)
	for i := 0; i < v; i++ {
		m[i] = make(map[int]int)
	}
	for i := 0; i < e; i++ {
		s, t, d := sc.NextInt(), sc.NextInt(), sc.NextInt()
		m[s][t] = d
	}
	pq := make(PriorityQueueStatus, 0)
	start := &Status{
		MinCostStatus: MinCostStatus{
			Visited:   0,
			PrevPoint: 0,
		},
		Cost: 0,
	}
	memo := make(map[MinCostStatus]int)
	heap.Push(&pq, start)
	for pq.Len() > 0 {
		now := pq.Pop().(*Status)
		if now.Visited == (1<<uint(v))-1 {
			fmt.Println(now.Cost)
			return
		}
		for k, v := range m[now.PrevPoint] {
			if now.Visited&(1<<uint(k)) == 0 {
				minCostStatus := MinCostStatus{
					Visited:   now.Visited | (1 << uint(k)),
					PrevPoint: k,
				}
				cost := now.Cost + v
				if v, ok := memo[minCostStatus]; !ok || (ok && cost < v) {
					next := &Status{
						MinCostStatus: minCostStatus,
						Cost:          cost,
					}
					memo[minCostStatus] = cost
					heap.Push(&pq, next)
				}
			}
		}
	}
	fmt.Println(-1)
}

