#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
const int Maxn=50001;
const int INF=1000000000;
vector< pair<int,int> >v[Maxn];
int heap[Maxn],poz[Maxn],d[Maxn],l;
inline void up(int p)
{
    while(p<<1 && d[heap[p]]<d[heap[p<<1]])
    {
        swap(poz[heap[p<<1]],poz[heap[p]]);
        swap(heap[p<<1],heap[p]);
        p<<=1;
    }
}
inline void down(int p)
{
    int y;
    bool ok=true;
    while(2*p<=l && ok)
    {
        ok=false;y=2*p;
        if(d[heap[y]]>d[heap[y+1]])
            y++;
        if(d[heap[y]]<d[heap[p]])
        {
            swap(poz[heap[y]],poz[heap[p]]);
            swap(heap[y],heap[p]);
            p=y;ok=true;
        }
    }
}
inline void push(int x)
{
    heap[++l]=x;poz[x]=l;
    up(l);
}
inline void pop()
{
    swap(poz[heap[l]],poz[heap[1]]);
    swap(heap[l],heap[1]);
    l--;down(1);
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    int n,m,a,b,c;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        fscanf(fin,"%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
    }
    for(int i=2;i<=n;i++)
        d[i]=INF;
    push(1);
    for(int i=2;i<n;i++)
    {
        a=heap[1];pop();
        for(size_t j=0;j<v[a].size();j++)
        {
            b=v[a][j].first;c=v[a][j].second;
            if(d[b]>d[a]+c)
            {
                d[b]=d[a]+c;
                if(poz[b])
                    up(b);
                else
                    push(b);
            }
        }
    }
    for(int i=2;i<=n;i++)
        fprintf(fout,"%d ",d[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}