#include <fstream>
#include <vector>
#include <set>
#include <climits>

#define x first
#define y second

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,i,j,k,c,d[50001];
vector<pair<int,int>> l[50001];
set<pair<int,int>> s;
set<pair<int,int>>::iterator it;

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>j>>k>>c;
        l[j].push_back(make_pair(k,c));
    }

    for(i=2;i<=n;i++)
        d[i]=INT_MAX;
    d[1]=0;

    s.insert(make_pair(0,1));

    while(!s.empty()){
        k=s.begin()->y;
        s.erase(s.begin());
        for(i=0;i<l[k].size();i++){
            int vecin=l[k][i].x;
            int cost=l[k][i].y;
            if(d[vecin]>d[k]+l[k][i].y){
                s.erase(make_pair(d[vecin],vecin));
                d[vecin]=d[k]+l[k][i].y;
                s.insert(make_pair(d[k]+l[k][i].y,vecin));
            }
        }
    }

    for(i=2;i<=n;i++)
        if(d[i]==INT_MAX)
            fout<<"0 ";
        else
            fout<<d[i]<<" ";

    return 0;
}