#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define li long long
#define pii pair<int, int>
#define vi vector<int>
#define li long long

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)

const int MAXN = 2005;
const int INF = 2e9;

vector<pii> edges[MAXN];
int dist[MAXN];

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	forn(i, m) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		edges[x].pb({y, w});
	}
	fore(start, 1, n) {
		set<pii> order;
		fore(u, 1, n) {
			dist[u] = INF;
		}
		dist[start] = 0;
		int ans = INF;
		order.insert({0, start});
		while (!order.empty()) {
			pii f = *order.begin();
			order.erase(order.begin());
			int v = f.se;
			if (dist[v] != f.fi) {
				continue;
			}
			for (pii e : edges[v]) {
				int u = e.fi;
				if (dist[u] > dist[v] + e.se) {
					dist[u] = dist[v] + e.se;
					order.insert({dist[u], u});
				}
				if (u == start) {
					ans = min(ans, dist[v] + e.se);
				}
			}
		}
		if (ans == INF) {
			ans = -1;
		}
		printf("%d\n", ans);
	}
}
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

ll helper(ll a){
  vector<int> vec(10,0);
  while(a){
    vec[a%10]++;
    a/=10;
  }
  ll v1=0,v2=0;
  for(int i=0;i<10;i++){
    for(int j=0;j<vec[i];j++)v2=v2*10+i;
  }
  for(int i=9;i>=0;i--){
    for(int j=0;j<vec[i];j++)v1=v1*10+i;
  }
  return v1-v2;
}

void solve() {

  ll n,k;
  cin>>n>>k;
  while(k){
    ll tmp=helper(n);
    if(tmp==n){
      cout<<tmp<<endl;
      return;
    }
    n=tmp;
    k--;
  }
  cout<<n<<endl;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);

  int tc = 1;
  //cin >> tc;
  for (int t = 1; t <= tc; t++) {
    solve();
  }
}
