#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

#define NMAX 50005
#define DIM 1000

using namespace std;

int n,m,x,y,z;
int dist[NMAX];

queue <pair <int ,int > >q;
vector <pair <int ,int > >v[NMAX];

int poz=0;
char buff[DIM+5];

inline void citeste(int &numar)
{
    numar=0;
    while (buff[poz]<'0' || buff[poz]>'9')
       if ( ++poz==DIM)fread(buff,1,DIM,stdin),poz=0;

    while (buff[poz]>='0' && buff[poz]<='9')
    {
        numar=numar*10+buff[poz]-'0';
        if (++poz==DIM)fread(buff,1,DIM,stdin),poz=0;
    }
}
inline void dijkstra()
{
    for (int i=2;i<=n;i++)
     dist[i]=1<<20;
    q.push(make_pair(0,1));
    while (q.size())
     {
        int nod=q.front().second;
        q.pop();
        for (vector <pair <int ,int > >::iterator it=v[nod].begin();it!=v[nod].end();it++)
           if (dist[(*it).first]>dist[nod]+(*it).second)
            {
               dist[(*it).first]=dist[nod]+(*it).second;
               q.push(make_pair(-dist[(*it).first],(*it).first));
            }
     }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    citeste(n);
    citeste(m);

    for (int i=1;i<=m;i++)
     {
         citeste(x);
         citeste(y);
         citeste(z);
         v[x].push_back(make_pair(y,z));
     }
    dijkstra();
    for (int i=2;i<=n;i++)
      if (dist[i]<1<<20)printf("%d ",dist[i]);
      else printf("0 ");
    fclose(stdin);
    fclose(stdout);
}