#include <bits/stdc++.h>
const int MOD = 1000000007;
int n, m;
int N;
std::vector<std::vector<std::pair<int, int> > > g;
void bfs() {
  std::queue<int> que;
  que.push(0);
  std::vector<int> dist(N, 1000000000);
  dist[0] = 0;
  while ((int)(que).size()) {
    int v = que.front();
    que.pop();
    for (int i = 0; i < ((int)(g[v]).size()); ++i) {
      int to = g[v][i].first;
      if (dist[to] < dist[v] + 1) {
        std::swap(g[v][i], g[v].back());
        g[v].pop_back();
        i--;
      } else if (dist[to] > dist[v] + 1) {
        dist[to] = dist[v] + 1;
        que.push(to);
      }
    }
  }
}
std::vector<int> ans;
void bfs2() {
  ans.resize(N, -1);
  ans[0] = 0;
  std::vector<bool> vis(N);
  std::queue<std::vector<int> > que;
  que.push(std::vector<int>{0});
  vis[0] = true;
  while ((int)(que).size()) {
    std::vector<int> vec = que.front();
    que.pop();
    for (int val = 0; val < (10); ++val) {
      std::vector<int> now;
      for (auto &cur : (vec)) {
        for (auto &ch : (g[cur]))
          if (ch.second == val && vis[ch.first] == false) {
            ans[ch.first] = (10ll * ans[cur] + ch.second) % MOD;
            vis[ch.first] = true;
            now.push_back(ch.first);
          }
      }
      if ((int)(now).size()) que.push(now);
    }
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cin >> n >> m;
  g.resize(n);
  for (int xd = (1); xd < (m + 1); ++xd) {
    int a, b;
    std::cin >> a >> b;
    a--;
    b--;
    std::string s = std::to_string(xd);
    int last = a;
    for (int i = 0; i < ((int)(s).size()); ++i) {
      g.emplace_back();
      int next = (int)(g).size() - 1;
      if (i == (int)(s).size() - 1) next = b;
      g[last].push_back(std::make_pair(next, s[i] - '0'));
      g[next].push_back(std::make_pair(last, s[(int)(s).size() - 1 - i] - '0'));
      last = next;
    }
  }
  N = (int)(g).size();
  bfs();
  bfs2();
  for (int i = (1); i < (n); ++i) std::cout << ans[i] << "\n";
  return 0;
}
