// time-limit: 2000
// problem-url: https://atcoder.jp/contests/abc185/tasks/abc185_e
#include <bits/stdc++.h>

#define endl "\n"
#define int long long
#define double long double
#define precise \
    fixed << setprecision(12)
#define debug(var) \
    if (debugging) \
    cerr << (#var) << ": " << var << endl

const bool debugging = 1;
const int mod = 1e9 + 7;

using namespace std;

template <class T>
ostream &operator<<(ostream &os, vector<T> V)
{
    for (auto v : V)
    {
        os << v << " ";
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, vector<vector<T>> V)
{
    for (int i = 0; i < V.size(); i++)
    {
        for (int j = 0; j < V[i].size(); j++)
        {
            os << V[i][j] << " ";
        }
        os << endl;
    }
    return os << "";
}

template <class T>
ostream &operator<<(ostream &os, set<T> S)
{
    for (auto s : S)
    {
        os << s << " ";
    }
    return os << "";
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P)
{
    return os << P.first << " " << P.second;
}

template <class L, class R>
ostream &operator<<(ostream &os, map<L, R> M)
{
    os << endl;
    for (auto m : M)
    {
        os << m << endl;
    }
    return os << "";
}

const int max_val = 1e3 + 10;

int dp[max_val][max_val];
int N, M;
vector<int> arr1;
vector<int> arr2;

int recur(int ptr1, int ptr2)
{
    if (ptr1 == N || ptr2 == M)
    {
        return (N - ptr1) + (M - ptr2);
    }

    if (dp[ptr1][ptr2] != -1)
    {
        return dp[ptr1][ptr2];
    }

    dp[ptr1][ptr2] = INT64_MAX;
    dp[ptr1][ptr2] = min(dp[ptr1][ptr2], 1 + recur(ptr1 + 1, ptr2));
    dp[ptr1][ptr2] = min(dp[ptr1][ptr2], 1 + recur(ptr1, ptr2 + 1));
    dp[ptr1][ptr2] = min(dp[ptr1][ptr2], (arr1[ptr1] != arr2[ptr2]) + recur(ptr1 + 1, ptr2 + 1));
    return dp[ptr1][ptr2];
}

void solve()
{
    cin >> N >> M;
    arr1.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> arr1[i];
    }

    arr2.resize(M);
    for (int i = 0; i < M; i++)
    {
        cin >> arr2[i];
    }

    fill_n(&dp[0][0], max_val * max_val, -1);
    cout << recur(0, 0) << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int no_of_testcases = 1;
    // cin >> no_of_testcases;
    while (no_of_testcases-- > 0)
    {
        solve();
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;
const int MOD = 1000000007;
const double pi = acos(-1);
ll gcd(ll a, ll b) {if(b == 0) return a; else return gcd(b,a%b);}
ll lcm(ll a, ll b) {return a*b/gcd(a,b);}

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}
    constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}
    constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}
    constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}
    constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}
    constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {return os << x.val;}
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {if (n == 0) return 1;auto t = modpow(a, n / 2);t = t * t;if (n & 1) t = t * a;return t;}
};


const ll INF = 1LL<<60;

struct edge
{
    int to;
    ll cost;
};


void dijkstra(const vector<vector<edge>> &G, int s , vector<ll> &dist)
{
    priority_queue<P,vector<P>,greater<P>> que;
    dist[s] = 0;
    que.push(P(0,s));

    while(!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        int d =  p.first;
        //if(dist[v] < d) continue;
        for(auto e : G[v]) {
            if(dist[e.to] > dist[v]+e.cost) {
                dist[e.to] = dist[v] + e.cost;
                que.push(P(dist[e.to],e.to));
            }
        }
    }
}

using mint = Fp<MOD>;

int main() {
    int N,M; cin >> N >> M;

    vecl d(N);
    REP(i,N) d[i] = INF;
    vecvecl dist(N,vecl(N, INF));
    vector<vector<edge>> G1(N, vector<edge>());

    REP(i,M) {
        int a,b; cin >> a >> b;
        --a,--b;
        ll t; cin >> t;
        if(a != b) G1[a].push_back({b,t});
        if(a == b) d[a] = min(d[a],t);
    }

    REP(s,N) {
        vector<ll> dist1(20010, INF);
        dijkstra(G1,s,dist1);
        REP(t,N) {
            dist[s][t] = min(dist[s][t],dist1[t]);
        }
    }

    // REP(i,N) {
    //     REP(j,N) cout << dist[i][j] << " ";
    //     cout << endl;
    // }

    REP(s,N) {
        ll ans = INF;
        REP(t,N) {
            if(s!=t) if(dist[s][t] == INF || dist[t][s] == INF) continue; else chmin(ans,dist[s][t] + dist[t][s]);
        }
        if(ans == INF) {
            if(d[s] != INF) cout << d[s] << endl;
            else cout << -1 << endl;
        } else {
            if(d[s] != INF) cout << min(ans,d[s]) << endl;
            else cout << ans << endl;
        }
    }


    return 0;
}