#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
// --------------------------------------------------------
template<class T> bool chmax(T& a, const T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T b) { if (b < a) { a = b; return 1; } return 0; }
#define FOR(i,l,r) for (ll i = (l); i < (r); ++i)
#define RFOR(i,l,r) for (ll i = (r)-1; (l) <= i; --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUMLL(c) accumulate(ALL(c), 0LL)
#define SZ(c) ((ll)(c).size())
#define BIT(b,i) (((b)>>(i)) & 1)
#define PCNT(b) __builtin_popcountll(b)
#define CIN(c) cin >> (c)
#define COUT(c) cout << (c) << '\n'
#define debug(x) cerr << "l." << __LINE__ << " : " << #x << " = " << (x) << '\n'
ll llceil(ll a, ll b) { return (a + b - 1) / b; }
string toupper(const string& S) { string T(S); REP(i,SZ(T)) T[i] = toupper(T[i]); return T; }
string tolower(const string& S) { string T(S); REP(i,SZ(T)) T[i] = tolower(T[i]); return T; }
using P = pair<ll,ll>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VVS = vector<VS>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VVVLL = vector<VVLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VVVD = vector<VVD>;
using VLD = vector<ld>;
using VVLD = vector<VLD>;
using VVVLD = vector<VVLD>;
static const double EPS = 1e-10;
static const double PI  = acos(-1.0);
static const ll MOD = 1000000007;
// static const ll MOD = 998244353;
static const ll INF = (1LL << 62) - 1;  // 4611686018427387904 - 1
// --------------------------------------------------------
// #include <atcoder/all>
// using namespace atcoder;

// Editorial AC

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    ll N, M; cin >> N >> M;
    VVP G(N);
    REP(_,M) {
        ll u, v, c; cin >> u >> v >> c;
        u--; v--;
        G[u].push_back(P(v, c));
        G[v].push_back(P(u, c));
    }

    VLL C(N,-1); C[0] = 1;
    queue<ll> q; q.push(0);
    while (!q.empty()) {
        ll u = q.front(); q.pop();
        for (auto& [v, c] : G[u]) {
            if (C[v] != -1) continue;
            if (C[u] == c) {
                C[v] = (c == N ? 1 : c+1);
            } else {
                C[v] = c;
            }
            q.push(v);
        }
    }

    REP(i,N) COUT(C[i]);

    return 0;
}

#include <bits/stdc++.h>          
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repp(i, st, en) for (ll i = (ll)st; i < (ll)(en); i++)
#define repm(i, st, en) for (ll i = (ll)st; i >= (ll)(en); i--)
#define all(v) v.begin(), v.end()
void chmax(ll &x, ll y) {x = max(x,y);}
void chmin(ll &x, ll y) {x = min(x,y);}
void Yes() {cout << "Yes" << endl; exit(0);}
void No() {cout << "No" << endl; exit(0);}
template<class in_Cout> void Cout(in_Cout x) {cout << x << endl; exit(0);}

const ll inf = 1e18;
const ll mod = 1e9 + 7;

int main() {
    ll N, X; cin >> N >> X;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];

    ll ans = inf;
    rep(i,N) chmin(ans,X-A[i]);
    for (ll k=2; k<=N; k++) {
        // dp[i][j][k] : A[i]まで見たときj種類使って余りがlである最大値
        vector<vector<vector<ll>>> dp(N,vector<vector<ll>>(k+1,vector<ll>(k,-inf)));
        rep(i,N) dp[i][0][0] = 0LL;
        dp[0][1][A[0]%k] = A[0];
        for (ll i=0; i<N-1; i++) {
            ll a = A[i+1];
            rep(j,k+1) rep(l,k) {
                if (dp[i][j][l]==-inf) continue;
                // 使わない
                chmax(dp[i+1][j][l],dp[i][j][l]);
                if (j+1>k) continue;
                // 使う
                chmax(dp[i+1][j+1][(l+a)%k],dp[i][j][l]+a);
            }
        }
        ll S = dp[N-1][k][X%k];
        if (S==-inf) continue;
        chmin(ans,(X-S)/k);
    }

    cout << ans << endl;
}