#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

class iparser{
    public:
        iparser() {}
        iparser(const char *file_name){
            input_file.open(file_name);
            cursor=0;
            input_file.read(buffer,SIZE);}
        inline iparser &operator >>(int &n){
            while(buffer[cursor]<'0' or buffer[cursor]>'9') inc();
            n=0;
            while('0'<=buffer[cursor] and buffer[cursor]<='9')
                n=n*10+buffer[cursor]-'0',inc();
            return *this;}
    private:
        ifstream input_file;
        static const int SIZE=0x8000;
        char buffer[SIZE];
        int cursor=0;
        inline void inc(){
            if(++cursor==SIZE)
                cursor=0,input_file.read(buffer,SIZE);
        }
};

struct edge{
    int nod,c;
    bool operator <(const edge &aux) const
        {return c>aux.c;}
};

vector <edge> v[50010];
priority_queue <edge> heap;
int d[50010],n;

void dijkstra(int nod){
    for(int i=1;i<=n;++i) d[i]=INFINITY;
    d[nod]=0;
    heap.push({nod,0});
    while(!heap.empty()){
        int nod=heap.top().nod,c=heap.top().c;
        heap.pop();
        if(d[nod]!=c) continue;
        for(vector <edge>::iterator i=v[nod].begin();i<v[nod].end();advance(i,1))
            if(d[i->nod]>d[nod]+i->c)
                d[i->nod]=d[nod]+i->c,heap.push({i->nod,d[i->nod]});
    }
}

int main()
{
    iparser f ("dijkstra.in");
    ofstream t ("dijkstra.out");
    int x,y,c,m;
    f>>n>>m;
    for (int i=0;i<m;++i)
        f>>x>>y>>c,v[x].push_back({y,c});
    dijkstra(1);
    for(int i=2;i<=n;++i)
        if(d[i]==INFINITY) t<<"0 ";
        else t<<d[i]<<" ";
    return 0;
}