#include <bits/stdc++.h>
using namespace std;
int sz(int num) {
  string cad = to_string(num);
  return cad.size();
}
int contg;
const int MAXN = 1.1e6 + 100;
vector<pair<int, int>> L[MAXN];
vector<pair<int, int>> LL[MAXN];
int D[MAXN];
const long long MOD = 1e9 + 7;
long long res[MAXN];
bool mk[MAXN];
bool mk2[MAXN];
int PW10[9];
bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) {
  string s1 = to_string(p1.first);
  string s2 = to_string(p2.first);
  return s1 < s2;
}
stack<pair<pair<int, int>, int>> st;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  PW10[0] = 1;
  for (int i = 1; i < 9; i++) {
    PW10[i] = PW10[i - 1] * 10 % MOD;
  }
  for (int i = 0; i < MAXN; i++) {
    D[i] = 1e9;
  }
  int N, M;
  cin >> N >> M;
  contg = N;
  for (int i = 1; i <= M; i++) {
    int a, b;
    cin >> a >> b;
    string cad = to_string(i);
    int temp = a;
    for (int x = 0; x < cad.size(); x++) {
      if (x == cad.size() - 1) {
        L[temp].push_back({cad[x] - '0', b});
      } else {
        L[temp].push_back({cad[x] - '0', ++contg});
        temp = contg;
      }
    }
    temp = b;
    for (int x = 0; x < cad.size(); x++) {
      if (x == cad.size() - 1) {
        L[temp].push_back({cad[x] - '0', a});
      } else {
        L[temp].push_back({cad[x] - '0', ++contg});
        temp = contg;
      }
    }
  }
  for (int i = 1; i < MAXN; i++) {
    sort(L[i].begin(), L[i].end(), cmp);
  }
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      Q;
  D[1] = 0;
  Q.push({0, 1});
  while (Q.size()) {
    int nodo = Q.top().second;
    Q.pop();
    for (auto v : L[nodo]) {
      if (D[nodo] + sz(v.first) < D[v.second]) {
        D[v.second] = D[nodo] + sz(v.first);
        Q.push({D[v.second], v.second});
      }
    }
  }
  for (int i = 1; i < MAXN; i++) {
    for (auto v : L[i]) {
      if (D[i] + sz(v.first) == D[v.second]) {
        LL[i].push_back(v);
      }
    }
  }
  st.push({{0, 0}, 1});
  mk[1] = true;
  while (!st.empty()) {
    pair<int, int> tope = st.top().first;
    int nodo = st.top().second;
    vector<int> temp;
    while (st.size() && st.top().first == tope) {
      temp.push_back(st.top().second);
      st.pop();
    }
    vector<pair<int, int>> tG, G;
    for (auto x : temp) {
      for (auto v : LL[x]) {
        if (!mk[v.second]) {
          tG.push_back({v.first, v.second});
        }
      }
    }
    sort(tG.begin(), tG.end());
    for (int i = 0; i < tG.size(); i++) {
      false;
      if (!mk2[tG[i].second]) {
        G.push_back(tG[i]);
        mk2[tG[i].second] = true;
      }
    }
    for (auto x : G) {
      false;
      mk2[x.second] = false;
      mk[x.second] = true;
    }
    for (int i = G.size() - 1; i >= 0; i--) {
      res[G[i].second] = (res[nodo] * 10ll + G[i].first) % MOD;
      st.push({{G[i].first, tope.second + 1}, G[i].second});
    }
    false;
  }
  for (int i = 2; i <= N; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}
