package main

import (
	"io"
	"os"
	"strconv"
)

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int {
		for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
			idx++
		}
		val := 0
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			val = val*10 + int(data[idx]-'0')
			idx++
		}
		return val
	}

	n := nextInt()
	m := nextInt()

	const INF int64 = 1 << 60

	exact := make([]int64, n*n)
	for i := range exact {
		exact[i] = INF
	}

	for i := 0; i < m; i++ {
		a := nextInt()
		b := nextInt()
		c := int64(nextInt())
		pos := a*n + b
		if c < exact[pos] {
			exact[pos] = c
		}
	}

	trans := make([]int64, n*n)
	for a := 0; a < n; a++ {
		off := a * n
		prev := INF
		for p := 0; p < 2*n; p++ {
			v := exact[off+p%n]
			if prev+1 < v {
				v = prev + 1
			}
			prev = v
			if p >= n {
				trans[off+p-n] = v
			}
		}
	}

	dist := make([]int64, n)
	used := make([]bool, n)
	out := make([]byte, 0, n*n*14)
	modN := int64(n)

	for s := 0; s < n; s++ {
		for i := 0; i < n; i++ {
			dist[i] = INF
			used[i] = false
		}
		dist[s] = 0

		for it := 0; it < n; it++ {
			u := -1
			best := INF
			for i := 0; i < n; i++ {
				if !used[i] && dist[i] < best {
					best = dist[i]
					u = i
				}
			}
			if u < 0 {
				break
			}
			used[u] = true

			off := u * n
			r := int(best % modN)

			for x := 0; x < r; x++ {
				cand := best + trans[off+n-r+x]
				if cand < dist[x] {
					dist[x] = cand
				}
			}
			for x := r; x < n; x++ {
				cand := best + trans[off+x-r]
				if cand < dist[x] {
					dist[x] = cand
				}
			}
		}

		for j := 0; j < n; j++ {
			if j > 0 {
				out = append(out, ' ')
			}
			out = strconv.AppendInt(out, dist[j], 10)
		}
		out = append(out, '\n')
	}

	os.Stdout.Write(out)
}