#include <fstream>
#include <vector>
using namespace std;

const int N=50005,inf=1<<30;
int dist[N],n;
bool use[N];
struct Muchie{
    int y,c;
};
vector<Muchie> a[N];
vector<int> etc;

struct Heap{
    vector<int> &v;
    bool (*cmp)(int,int);

    inline void sch(int &a,int &b){
        int c=a;a=b;b=c;
    }
    void push(int x){
        if (v.empty())
            v.push_back(0);
        v.push_back(x);
        for (x=v.size()-1;x>1 && cmp(v[x],v[x>>1]);x>>=1)
            sch(v[x],v[x>>1]);
    }
    void pop(){
        v[1]=v.back();
        v.pop_back();
        for (int x=0,m=1;m!=x;)
        {
            x=m;
            for (int S=x<<1;S<=(x<<1)+1;S++)
                if (S<v.size() && cmp(v[S],v[m]))
                    m=S;
            if (x!=m)
                sch(v[x],v[m]);
        }
    }
    void pop(int &x){
        x=v[1];
        pop();
    }
    inline bool empty(){
        return v.size()==1;
    }
    inline int top(){
        return v[1];
    }
};

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

inline bool cmp(int a,int b){
    return dist[a] <= dist[b];
}

void dijkstra(int x){
    int y,c;
    for (int i=1;i<N;i++)
    {
        dist[i]=inf;
        use[i]=false;
    }
    dist[x]=0;
    Heap H=(Heap){etc,cmp};
    H.push(x);
    while (!H.empty()){
        H.pop(x);
        if (use[x])
            continue;
        use[x]=true;
        for (vector<Muchie>::iterator i=a[x].begin();i!=a[x].end();i++){
            y=(*i).y;
            c=(*i).c+dist[x];
            if (dist[y]>c){
                dist[y]=c;
                H.push(y);
            }
        }
    }
}

int main(){
    int m,x,y,c;
    in>>n>>m;
    while (m--){
        in>>x>>y>>c;
        a[x].push_back((Muchie){y,c});
    }
    dijkstra(1);
    for (int i=2;i<=n;i++)
        out<<(dist[i]!=inf ? dist[i] : 0)<<" ";
    out<<"\n";
    return 0;
}