package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
	"sort"
)

type Edge struct {
	a, b int
	d    int64
}

type Bits [3]uint64

func setBit(b *Bits, i int) {
	b[i>>6] |= 1 << (uint(i) & 63)
}

func isEmpty(b Bits) bool {
	return b[0] == 0 && b[1] == 0 && b[2] == 0
}

func addEdge(rows []Bits, adj, rev [][]int, u, v int) {
	if ((rows[u][v>>6] >> (uint(v) & 63)) & 1) != 0 {
		return
	}
	rows[u][v>>6] |= 1 << (uint(v) & 63)
	adj[u] = append(adj[u], v)
	rev[v] = append(rev[v], u)
}

func shortestToTarget(s Bits, rev [][]int, target, n int) int {
	if isEmpty(s) {
		return -1
	}
	if ((s[target>>6] >> (uint(target) & 63)) & 1) != 0 {
		return 0
	}
	dist := make([]int, n)
	for i := 0; i < n; i++ {
		dist[i] = -1
	}
	q := make([]int, n)
	head, tail := 0, 0
	dist[target] = 0
	q[tail] = target
	tail++
	for head < tail {
		v := q[head]
		head++
		for _, u := range rev[v] {
			if dist[u] == -1 {
				dist[u] = dist[v] + 1
				q[tail] = u
				tail++
			}
		}
	}
	best := -1
	x := s[0]
	for x != 0 {
		t := bits.TrailingZeros64(x)
		i := t
		if i < n && dist[i] != -1 && (best == -1 || dist[i] < best) {
			best = dist[i]
		}
		x &= x - 1
	}
	x = s[1]
	for x != 0 {
		t := bits.TrailingZeros64(x)
		i := 64 + t
		if i < n && dist[i] != -1 && (best == -1 || dist[i] < best) {
			best = dist[i]
		}
		x &= x - 1
	}
	x = s[2]
	for x != 0 {
		t := bits.TrailingZeros64(x)
		i := 128 + t
		if i < n && dist[i] != -1 && (best == -1 || dist[i] < best) {
			best = dist[i]
		}
		x &= x - 1
	}
	return best
}

func square(prev []Bits, n int) []Bits {
	next := make([]Bits, n)
	for i := 0; i < n; i++ {
		var row Bits
		x := prev[i][0]
		for x != 0 {
			t := bits.TrailingZeros64(x)
			j := t
			row[0] |= prev[j][0]
			row[1] |= prev[j][1]
			row[2] |= prev[j][2]
			x &= x - 1
		}
		x = prev[i][1]
		for x != 0 {
			t := bits.TrailingZeros64(x)
			j := 64 + t
			if j < n {
				row[0] |= prev[j][0]
				row[1] |= prev[j][1]
				row[2] |= prev[j][2]
			}
			x &= x - 1
		}
		x = prev[i][2]
		for x != 0 {
			t := bits.TrailingZeros64(x)
			j := 128 + t
			if j < n {
				row[0] |= prev[j][0]
				row[1] |= prev[j][1]
				row[2] |= prev[j][2]
			}
			x &= x - 1
		}
		next[i] = row
	}
	return next
}

func apply(vec Bits, mat []Bits, n int) Bits {
	var res Bits
	x := vec[0]
	for x != 0 {
		t := bits.TrailingZeros64(x)
		i := t
		res[0] |= mat[i][0]
		res[1] |= mat[i][1]
		res[2] |= mat[i][2]
		x &= x - 1
	}
	x = vec[1]
	for x != 0 {
		t := bits.TrailingZeros64(x)
		i := 64 + t
		if i < n {
			res[0] |= mat[i][0]
			res[1] |= mat[i][1]
			res[2] |= mat[i][2]
		}
		x &= x - 1
	}
	x = vec[2]
	for x != 0 {
		t := bits.TrailingZeros64(x)
		i := 128 + t
		if i < n {
			res[0] |= mat[i][0]
			res[1] |= mat[i][1]
			res[2] |= mat[i][2]
		}
		x &= x - 1
	}
	return res
}

func advanceExact(s Bits, rows []Bits, n int, steps int64) Bits {
	if steps == 0 {
		return s
	}
	maxP := 0
	for x := steps; x > 0; x >>= 1 {
		maxP++
	}
	pows := make([][]Bits, maxP)
	pows[0] = make([]Bits, n)
	copy(pows[0], rows)
	for i := 1; i < maxP; i++ {
		pows[i] = square(pows[i-1], n)
	}
	cur := s
	bit := 0
	for steps > 0 {
		if (steps & 1) != 0 {
			cur = apply(cur, pows[bit], n)
			if isEmpty(cur) {
				return cur
			}
		}
		steps >>= 1
		bit++
	}
	return cur
}

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

	var n, m int
	if _, err := fmt.Fscan(in, &n, &m); err != nil {
		return
	}

	edges := make([]Edge, m)
	for i := 0; i < m; i++ {
		var a, b int
		var d int64
		fmt.Fscan(in, &a, &b, &d)
		edges[i] = Edge{a - 1, b - 1, d}
	}

	sort.Slice(edges, func(i, j int) bool {
		if edges[i].d != edges[j].d {
			return edges[i].d < edges[j].d
		}
		if edges[i].a != edges[j].a {
			return edges[i].a < edges[j].a
		}
		return edges[i].b < edges[j].b
	})

	rows := make([]Bits, n)
	adj := make([][]int, n)
	rev := make([][]int, n)

	idx := 0
	for idx < m && edges[idx].d == 0 {
		addEdge(rows, adj, rev, edges[idx].a, edges[idx].b)
		idx++
	}

	var cur Bits
	setBit(&cur, 0)
	var flights int64 = 0

	for idx < m {
		nextD := edges[idx].d
		gap := nextD - flights

		dist := shortestToTarget(cur, rev, n-1, n)
		if dist != -1 && int64(dist) <= gap {
			fmt.Fprintln(out, flights+int64(dist))
			return
		}

		cur = advanceExact(cur, rows, n, gap)
		if isEmpty(cur) {
			fmt.Fprintln(out, "Impossible")
			return
		}

		flights = nextD
		for idx < m && edges[idx].d == flights {
			addEdge(rows, adj, rev, edges[idx].a, edges[idx].b)
			idx++
		}
	}

	dist := shortestToTarget(cur, rev, n-1, n)
	if dist == -1 {
		fmt.Fprintln(out, "Impossible")
	} else {
		fmt.Fprintln(out, flights+int64(dist))
	}
}