#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repi(i, a, b) for(int i=(a); i>(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define ll long long
#define gcd __gcd
#define eb emplace_back
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define fi first
#define se second
#define pqueue priority_queue
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define PI acos(-1.0)
#define EPS 1e-9
#define mod 1000000007
using namespace std;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
template<typename T1, typename T2>
ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << '(' << p.fi << ", " << p.se << ')'; }
template<typename T>
void printv(const T& v) { for(auto i : v) cerr << i << ' '; cerr << '\n'; }
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxpq = priority_queue<T>;
//All indexing is 0-based
using namespace __gnu_pbds;
template<class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
//methods: find_by_order(k); & order_of_key(k);
//To make it an ordered_multiset, use pairs of (value, time_of_insertion)
//to distinguish values which are similar
template<class key, class value, class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
//Returns no. of values x for which ceil(n / x) == y (y must be > 1).
inline ll CC(ll n, ll y) { return iceil(n, y-1) - iceil(n, y); }
//Returns no. of values x for which floor(n / x) == y
inline ll FF(ll n, ll y) { return n / y - n / (y+1); }
//a and b are assumed to be taken modulo p
inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c; }
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c; }
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p; }
#define N 1000005
// #define int ll
// #define trace(...) 42
int n, nn, m;
vi adj[N][10];
int nxt[N][10];
void add_edge(int u, int v, int x) {
// trace(u, v, x);
int y = 0, len = 0;
while(x) {
++len;
y *= 10;
y += x % 10;
x /= 10;
}
int cur = u;
while(len > 1) {
int d = y % 10; y /= 10;
if(adj[cur][d].empty()) adj[cur][d].pb(n++);
// if(nxt[cur][d] == -1) nxt[cur][d] = n++;
// adj[cur][d].pb(nxt[cur][d]);
nxt[cur][d] = adj[cur][d].front();
cur = nxt[cur][d];
// cur = adj[cur][d].front();
// trace(kk, cur, d);
--len;
}
// if(count(all(adj[cur][y]), v) == 0) {
// trace(cur, v, y);
adj[cur][y].pb(v);
// }
}
int lvl[N];
ll dis[N];
bool vis[N];
void bfs(int src) {
lvl[src] = dis[src] = 0;
vis[src] = 1;
queue<int> q;
q.push(src); q.push(0); q.push(0);
while(q.size()) {
int i = q.front(); q.pop();
int l = q.front(); q.pop();
int d = q.front(); q.pop();
vi v = {i};
// for(int k = 0; k < 10; k++) {
// vi v;
// for(int j : adj[i][k]) {
// if(vis[j]) continue;
// v.pb(j);
// vis[j] = 1;
// lvl[j] = l + 1;
// dis[j] = (d * 10ll + k) % mod;
// // q.push(j); q.push(lvl[j]); q.push(dis[j]);
// }
// //Process all in parallel by merging their adjacency lists
// //into the first one
// if(v.size()) {
// int u = v.front();
// rep(i, 1, v.size()) {
// int j = v[i];
// rep(k, 0, 10) {
// for(int x : adj[j][k]) {
// adj[u][k].pb(x);
// }
// }
// }
// rep(k, 0, 10) uni(adj[u][k]);
// int j = u;
// q.push(j); q.push(lvl[j]); q.push(dis[j]);
// }
// }
while(q.size() && dis[q.front()] == d) {
v.pb(q.front());
q.pop(); q.pop(); q.pop();
}
for(int k = 0; k < 10; k++) {
for(int i : v) {
for(int j : adj[i][k]) {
if(!vis[j]) {
vis[j] = 1;
lvl[j] = l + 1;
dis[j] = (d * 10ll + k) % mod;
q.push(j); q.push(lvl[j]); q.push(dis[j]);
}
}
}
}
}
rep(i, 1, nn) {
// trace(i, lvl[i], dis[i]);
cout << dis[i] << '\n';
}
// rep(i, 0, n) {
// for(int k = 0; k < 10; k++) {
// for(int j : adj[i][k]) {
// trace(i, j, k);
// }
// }
// }
}
main()
{
#ifndef ONLINE_JUDGE
freopen("/home/tarun/Desktop/input.txt", "r", stdin);
// freopen("/home/tarun/Desktop/output.txt", "w", stdout);
#endif
sync;
clock_t clk = clock();
cerr << "I will return...\n";
memset(nxt, -1, sizeof nxt);
cin >> n >> m;
nn = n;
rep(i, 0, m) {
int u, v; cin >> u >> v;
--u, --v;
add_edge(u, v, i+1);
add_edge(v, u, i+1);
}
bfs(0);
cerr << "...don't you ever hang your head.\n";
cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / cps << '\n';
}
//Compile using:
//g++ -o filename.exe --std=c++11 filename.cpp
//Use -D CP for defining a macro CP in the local environment