#include <fstream>
#include <vector>
#define NMAX 50005
#define INF 9999999
using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int n,m;
int cost[1001][1001];
int d[NMAX];
int c[5*NMAX];
int p,u;

void belf(int nod)
{
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[nod]=0;
    p=u=1;
    c[u]=nod;
    while(p<=u)
    {
        int j=c[p];
        p++;
        for(int i=1;i<=n;i++)
            if(cost[j][i]!=INF)
        {
            if(d[i]>d[j]+cost[j][i])
            {
                d[i]=d[j]+cost[j][i];
                c[++u]=i;
            }
        }
    }
}

int main()
{
   f>>n>>m;
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        cost[i][j]=INF;
   for(int i=1;i<=m;i++)
   {
       int x,y,z;
       f>>x>>y>>z;
       cost[x][y]=z;
   }
   belf(1);
   for(int i=2;i<=n;i++)
    g<<d[i]<<" ";
   f.close();
   g.close();
    return 0;
}