#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
const int MOD = 1000000007;
using Edge = pair<int, long long>;
using Graph = vector<vector<Edge> >;
void dfs(const Graph &G, vector<int> vs, vector<long long> &res,
         const vector<int> &dist) {
  for (int w = 0; w < 10; ++w) {
    vector<int> nvs;
    for (auto v : vs) {
      for (auto e : G[v]) {
        if (e.second != w) continue;
        if (dist[e.first] != dist[v] + 1) continue;
        if (res[e.first] != -1) continue;
        res[e.first] = (res[v] * 10 + e.second) % MOD;
        nvs.push_back(e.first);
      }
    }
    if (!nvs.empty()) dfs(G, nvs, res, dist);
  }
}
int main() {
  int N, M;
  cin >> N >> M;
  Graph G(N + M * 6);
  int iN = N;
  for (long long w = 1; w <= M; ++w) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    vector<int> nodes;
    nodes.push_back(u);
    long long w2 = w;
    while (w2 >= 10) {
      w2 /= 10;
      nodes.push_back(N++);
    }
    nodes.push_back(v);
    w2 = w;
    int s = (int)nodes.size();
    for (int i = 0; i + 1 < s; ++i) {
      G[nodes[s - i - 2]].push_back({nodes[s - i - 1], w2 % 10});
      G[nodes[i + 1]].push_back({nodes[i], w2 % 10});
      w2 /= 10;
    }
  }
  for (int v = 0; v < N; ++v) {
    sort(G[v].begin(), G[v].end(),
         [&](Edge a, Edge b) { return a.second < b.second; });
  }
  vector<int> dist(N, -1);
  queue<int> que;
  que.push(0);
  dist[0] = 0;
  while (!que.empty()) {
    auto v = que.front();
    que.pop();
    for (auto e : G[v]) {
      if (dist[e.first] == -1) {
        dist[e.first] = dist[v] + 1;
        que.push(e.first);
      }
    }
  }
  vector<long long> res(N, -1);
  res[0] = 0;
  dfs(G, {0}, res, dist);
  for (int i = 1; i < iN; ++i) cout << res[i] << endl;
}
