#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
vector<pair<long long, char> > scores;
bool sco(long long i, long long j) { return (scores[i] < scores[j]); }
int main() {
  long long v, x, y, e, a, b, in = 0;
  pair<long long, char> h;
  cin >> v >> e;
  long long cont = v;
  vector<vector<pair<long long, char> > > grafo(
      880000, vector<pair<long long, char> >(0));
  for (int i = 0; i < e; i++) {
    cin >> x >> y;
    string X = to_string(i + 1);
    long long prev = x - 1, _prev = y - 1;
    for (int j = 0; j < X.length() - 1; j++) {
      grafo[prev].push_back(make_pair(cont, X[j]));
      prev = cont;
      cont++;
      grafo[_prev].push_back(make_pair(cont, X[j]));
      _prev = cont;
      cont++;
    }
    grafo[prev].push_back(make_pair(y - 1, X[X.length() - 1]));
    grafo[_prev].push_back(make_pair(x - 1, X[X.length() - 1]));
  }
  cont++;
  vector<bool> visitado(cont, false);
  vector<long long> dist(cont, 1e12);
  scores.assign(cont, {0, 'a'});
  vector<long long> ran(cont, -1);
  vector<long long> last(cont, 1e12);
  vector<long long> nex;
  long long prev = 1;
  ran[0] = 0;
  dist[0] = 0;
  last[0] = 0;
  queue<long long> q;
  q.push(0);
  nex.push_back(0);
  while (!nex.empty()) {
    nex.clear();
    while (!q.empty()) {
      long long t = q.front();
      q.pop();
      if (!visitado[t]) {
        visitado[t] = true;
        for (long long i = 0; i < grafo[t].size(); i++) {
          if (last[grafo[t][i].first] > last[t] + 1) {
            dist[grafo[t][i].first] =
                (dist[t] * 10 + (grafo[t][i].second - '0')) % mod;
            scores[grafo[t][i].first] = make_pair(ran[t], grafo[t][i].second);
            last[grafo[t][i].first] = last[t] + 1;
            nex.push_back(grafo[t][i].first);
          } else if (last[grafo[t][i].first] == last[t] + 1) {
            pair<long long, char> score = make_pair(ran[t], grafo[t][i].second);
            if (score < scores[grafo[t][i].first]) {
              scores[grafo[t][i].first] = score;
              dist[grafo[t][i].first] =
                  (dist[t] * 10 + (grafo[t][i].second - '0')) % mod;
            }
          }
        }
      }
    }
    if (nex.empty()) break;
    sort(nex.begin(), nex.end(), sco);
    prev++;
    long long r = 0;
    ran[nex[0]] = 0;
    q.push(nex[0]);
    for (int i = 1; i < nex.size(); i++) {
      if (scores[nex[i - 1]] != scores[nex[i]]) r++;
      ran[nex[i]] = r;
      q.push(nex[i]);
    }
  }
  for (int i = 1; i < v; i++) {
    cout << dist[i] << "\n";
  }
  return 0;
}
