#include <fstream>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,h[50001],k,dist[50011],m,x,y,z,ver[50011];
int oo=999999999;
vector<pair<int, int>>a[50001];
void update(int poz)
{
    while(dist[h[poz]]<dist[h[poz/2]])
    {
        swap(ver[h[poz]],ver[h[poz/2]]);
        swap(h[poz],h[poz/2]);
        poz/=2;
    }
}
void erase_heap()
{
    swap(ver[h[1]],ver[h[k]]);
    swap(h[1],h[k]);
    k--;
    int ok=1,cc=2,tt=1;
    while(cc<=k&&ok)
    {
        ok=0;
        if(cc!=k)
        {
            if(dist[h[cc]]>dist[h[cc+1]])
                cc++;
        }
        if(dist[h[cc]]<dist[h[tt]])
        {
            swap(ver[h[tt]],ver[h[cc]]);
            swap(h[tt],h[cc]);
            tt=cc;
            cc*=2;
            ok=1;
        }
    }
}
void add_heap(int val)
{
    h[++k]=val;
    int poz=k;
    update(poz);
}
void dijkstra(int s)
{
    dist[s]=0;
    ver[s]=1;
    h[++k]=s;
    while(k)
    {
        int u=h[1];
        erase_heap();
        int cost=dist[u];
        for(int i=0;i<a[u].size();i++)
        {
            int x1=a[u][i].first;
            int y1=a[u][i].second;
            if(dist[x1]>y1+cost)
            {
                if(dist[x1]==oo)
                {
                    ver[x1]=k+1;
                    dist[x1]=y1+cost;
                    add_heap(x1);
                }
                else
                {
                    dist[x1]=y1+cost;
                    update(ver[x1]);
                }
            }
        }
    }
}
int main()
{

    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
    }
    for(int i=1;i<=n;i++)
    {
        ver[i]=-1;
        dist[i]=oo;
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
        if(dist[i]==oo)
            g<<0<<" ";
        else
            g<<dist[i]<<" ";
    return 0;
}