#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);
    void push(int x)
    {
        if (v.empty())
            v.push_back(0);
        v.push_back(x);
        x=v.size()-1;
        while (x>1 && cmp(v[x],v[x>>1]))
        {
            int aux=v[x];
            v[x]=v[x>>1];
            v[x>>1]=aux;
            x>>=1;
        }
    }
    void pop(int &ret)
    {
        ret=v[1];
        v[1]=v.back();
        v.pop_back();
        int x=1,m=0,S;
        while (m!=x)
        {
            m=x;
            S=x<<1;
            if (S<v.size() && cmp(v[S],v[m]))
                m=S;
            S++;
            if (S<v.size() && cmp(v[S],v[m]))
                m=S;
            if (x!=m)
            {
                int aux=v[m];
                v[m]=v[x];
                v[x]=aux;
            }
        }
    }
    inline bool empty()
    {
        return v.size()==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;
}