#include <bits/stdc++.h>
#define DM 50005
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

queue<int>q;
int best[DM],n,m,a,b,c;
vector<pii>mch[DM];

int main()
{
    fin>>n>>m;
    while(m--){
        fin>>a>>b>>c;
        mch[a].pb({b,c});
    }
    q.push(1);
    for(int i=2;i<=n;++i) best[i]=INT_MAX;
    for(;!q.empty();q.pop()){
        int nod=q.front();
        for(auto i:mch[nod]){
            if(best[i.x]>best[nod]+i.y){
                best[i.x]=best[nod]+i.y;
                q.push(i.x);
            }
        }
    }
    for(int i=2;i<=n;++i) fout<<best[i]<<" ";
    return 0;
}