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

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

const int N=5e4;
const int INF=1 << 30;

struct muchii
{
    int vf;
    int c;
};

vector<muchii> ls[N+1];
int n, nh, h[N+1], poz[N+1], d[N+1];
bool selectat[N+1];

void schimb(int p1, int p2)
{
    swap(h[p1], h[p2]);
    poz[h[p1]]=p1;
    poz[h[p2]]=p2;
}

void urca(int p)
{
    while(p>1 && d[h[p]] < d[h[p/2]])
    {
        schimb(p, p/2);
        p/=2;
    }
}
void adauga(int x)
{
    h[++nh] = x;
    poz[x] = nh;
    urca(nh);
}

void coboara(int p)
{
    int fs=2*p, fd=2*p+1, bun = p;
    if(fs <= nh && d[h[fs]] < d[h[bun]])
    {
        bun=fs;
    }
    if(fd <= nh && d[h[fd]] < d[h[bun]])
    {
        bun=fd;
    }
    if(bun!=p)
    {
        schimb(bun, p);
        coboara(bun);
    }

}

void sterge()
{
    schimb(1, nh--);
    coboara(1);
}

void dijkstra(int x0)
{
    for(int i=1; i<=n; i++)
        d[i]=INF;
    d[x0]=0;
    adauga(x0);
    while(nh > 0) /// h nu este vid
    {
        int x = h[1]; ///varful
        sterge();
        selectat[x]=true;
        for(auto s: ls[x])
        {
            int y= s.vf;
            int c= s.c;
            if(selectat[y])
                continue;
            if(d[x] + c < d[y])
            {
                d[y] = d[x] + c;
                if(poz[y] == 0) ///daca y nu este inca in heap
                {
                    adauga(y);
                }
                else
                {
                    urca(poz[y]);
                }
            }
        }
    }
}


int main()
{
     int m;
     cin >> n >> m;
     for(int i=0; i<m; i++)
     {
         int x, y, c;
         cin >> x >> y >> c;
         ls[x].push_back((muchii){y, c});
     }
     dijkstra(1);
     for(int i=2; i<=n; i++)
     {
         if(d[i]==INF)
            d[i]=0;
         cout << d[i] << " ";
     }
     return 0;
}