#include <iostream>
#include <cstdio>
#include <queue>
#include <unordered_set>
#define task "SMST"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e2 + 5;
const ll Inf = 1e18 + 7;
int n, m;
ll d[N][N], ans;

unordered_set<int> adj[N];
int t = 0;

void Read(){
    cin >> n >> m;
}

void Setup(){
    for(int i = 2; i <= n; ++i){
        adj[i].insert(i - 1);
        adj[i - 1].insert(i);
    }
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            d[i][j] = d[j][i] = Inf;
}

struct Tque{
    int u, v;
    int now;
    ll w;
    Tque() {}
    Tque(int t, int i, int j, ll y){
        u = i;
        v = j;
        now = t;
        w = y;
    }
    bool operator < (const Tque &a) const{
        return w < a.w;
    }
};

void BFS(int x, int y, ll w){
    bool ck[N];
    fill_n(ck, N, 0);
    queue<Tque> s;
    s.push(Tque(x, x, x, -Inf));
    Tque res;
    while(s.size()){
        Tque c = s.front();
        s.pop();
        if(ck[c.now])
            continue;
        ck[c.now] = 1;
        if(c.now == y){
            res = c;
            if(w < res.w){
                adj[res.u].erase(res.v);
                adj[res.v].erase(res.u);
                adj[x].insert(y);
                adj[y].insert(x);
            }
            break;
        }
        for(auto i : adj[c.now]){
            if(d[i][c.now] > c.w)
                s.push(Tque(i, i, c.now, d[i][c.now]));
            else
                s.push(Tque(i, c.u, c.v, c.w));
        }
    }
}

bool ck[N];

ll Cal(int i){
    ck[i] = 1;
    ll ans = 0;
    for(auto j : adj[i]){
        if(ck[j])
            continue;
        ll res = Cal(j);
        ans = ans == Inf || d[i][j] == Inf || res == Inf ? Inf : d[i][j] + res + ans;
        if(ans == Inf)
            return Inf;
    }
    return ans;
}

void Solve(){

    while(m--){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        if(d[u][v] <= w)
            goto done;
        d[u][v] = d[v][u] = w;
        if(adj[u].find(v) != adj[u].end())
            goto done;
        BFS(u, v, w);
        done:;
        fill_n(ck, N, 0);
        ll ans = Cal(1);
        if(ans == Inf)
            cout << 123456789 << "\n";
        else
            cout << ans << "\n";
    }
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    Read();
    Setup();
    Solve();
}