#include<fstream>
#include<queue>
#include<vector>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int comp(const pii& i,const pii& j){

    return i.second>j.second;

}

int main(){

    int n,m;

    cin>>n>>m;

    vector<pii> G[50005];

    for(int i=1;i<=m;i++){

        int x,y,c;

        cin>>x>>y>>c;

        G[x].push_back(mp(y,c));

    }

    int d[50005];

    for(int i=1;i<=n;i++)
        d[i]=20005;

    priority_queue<pii,vector<pii>,greater<pii> > Q;

    Q.push(mp(0,1));

    while(!Q.empty()){

        int x=Q.top().first;
        int y=Q.top().second;

        Q.pop();

        if(x>=d[y]) continue;

        d[y]=x;

        for(int i=0;i<G[y].size();i++){

            int vec=G[y][i].first;
            int cost=G[y][i].second;

            if(d[y]+cost<d[vec])

                Q.push(mp(d[y]+cost,vec));

        }

    }

    for(int i=2;i<=n;i++)
        if(d[i]==20005) cout<<"0 ";
          else  cout<<d[i]<<' ';

}