package main

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

func main() {
	input, _ := io.ReadAll(os.Stdin)
	var pos int
	nextInt := func() int {
		for pos < len(input) && input[pos] <= ' ' {
			pos++
		}
		if pos >= len(input) {
			return 0
		}
		res := 0
		for pos < len(input) && input[pos] > ' ' {
			res = res*10 + int(input[pos]-'0')
			pos++
		}
		return res
	}

	n := nextInt()
	if n == 0 {
		return
	}
	m := nextInt()

	MAX_V := n + m*12 + 5
	head := make([]int32, MAX_V)
	to := make([]int32, 1, MAX_V*2)
	weight := make([]int8, 1, MAX_V*2)
	next := make([]int32, 1, MAX_V*2)

	addEdge := func(u, v int32, w int8) {
		to = append(to, v)
		weight = append(weight, w)
		next = append(next, head[u])
		head[u] = int32(len(to) - 1)
	}

	getDigits := func(x int) []int8 {
		var d []int8
		for x > 0 {
			d = append(d, int8(x%10))
			x /= 10
		}
		for i, j := 0, len(d)-1; i < j; i, j = i+1, j-1 {
			d[i], d[j] = d[j], d[i]
		}
		return d
	}

	nVertices := int32(n)
	for i := 1; i <= m; i++ {
		u := int32(nextInt())
		v := int32(nextInt())
		digits := getDigits(i)
		k := len(digits)
		if k == 1 {
			addEdge(u, v, digits[0])
			addEdge(v, u, digits[0])
		} else {
			prev := u
			for j := 0; j < k-1; j++ {
				nVertices++
				curr := nVertices
				addEdge(prev, curr, digits[j])
				prev = curr
			}
			addEdge(prev, v, digits[k-1])

			prev = v
			for j := 0; j < k-1; j++ {
				nVertices++
				curr := nVertices
				addEdge(prev, curr, digits[j])
				prev = curr
			}
			addEdge(prev, u, digits[k-1])
		}
	}

	dist := make([]int32, nVertices+1)
	for i := range dist {
		dist[i] = -1
	}
	val := make([]int64, nVertices+1)

	dist[1] = 0
	val[1] = 0
	L := [][]int32{{1}}

	for len(L) > 0 {
		var next_L [][]int32
		for _, S := range L {
			for c := int8(0); c <= 9; c++ {
				var NextS []int32
				for _, u := range S {
					for e := head[u]; e != 0; e = next[e] {
						if weight[e] == c {
							v := to[e]
							if dist[v] == -1 {
								dist[v] = dist[u] + 1
								val[v] = (val[u]*10 + int64(c)) % 1000000007
								NextS = append(NextS, v)
							}
						}
					}
				}
				if len(NextS) > 0 {
					next_L = append(next_L, NextS)
				}
			}
		}
		L = next_L
	}

	out := bufio.NewWriter(os.Stdout)
	for i := int32(2); i <= int32(n); i++ {
		out.WriteString(strconv.FormatInt(val[i], 10))
		if i < int32(n) {
			out.WriteByte(' ')
		}
	}
	out.WriteByte('\n')
	out.Flush()
}