#include<bits/stdc++.h>
using namespace std;
const int INF=1E9+7;
const int N=1E5+7;
int n,m;
struct stu{
    int a,b;
    bool friend operator <(const stu &x,const stu &y){
        return x.b>y.b;
    }
};
vector <stu >ve[N];
bool mark[N];
int dp[N];
int ans=-1;
void djstrea()
{
    priority_queue<stu>que;
    que.push({1,0});
    dp[1]=0;
    while(que.size()){
        stu x=que.top();
        que.pop();
        if (x.a==n){
            break;
        }
        if(mark[x.a]) continue ;
        mark[x.a]=1;
        for(int i=0;i<ve[x.a].size();i++){
            int dx=ve[x.a][i].a;
            int dy=ve[x.a][i].b;
            if(!mark[dx]&&dp[dx]>dp[x.a]+dy){
                dp[dx]=dp[x.a]+dy;
                que.push({dx,dp[dx]});
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    int x,y,z;
    for(int i=n;i>=1;i--) {
        ve[i].push_back({i-1,0});
    }
    for(int i=0;i<n;i++) dp[i]=INF;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        ve[x].push_back({y,z});
    }
    djstrea();
    if(dp[n]==INF)   cout<<-1<<endl;
    else cout<<dp[n]<<endl;
    for(int i=1;i<n;i++) cout<<dp[i]<<endl;
    return 0;
}
