#include <stdio.h>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;
FILE *f,*g;
struct name
{
    int a,b;
};

class compar
{
  public:
      bool operator() (name A,name B)
      {
          return (A.b > B.b);
      }
};
priority_queue <name, vector <name>,compar> q;

int start[50002],t[3][50002],cost[50002],drum[50002];
bitset <50002> viz;

int main()
{
    int m,n,k=0,x,y,c;
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        t[0][++k]=y;
        t[1][k]=start[x];
        start[x]=k;
        cost[k]=c;
    }
    for(int i=2;i<=n;++i)
        drum[i]=2000000000;
    q.push({1,0});
    int nod,vecin,dist,p;
    while(!q.empty())
    {
        name val;
        val=q.top();
        nod=val.a;
        q.pop();
        if(!viz[nod])
        {
            p=start[nod];
            while(p)
            {
                vecin=t[0][p];
                dist=cost[p]+drum[nod];
                if(dist<drum[vecin])
                {
                    drum[vecin]=dist;
                    q.push({vecin,dist});
                }
                p=t[1][p];
            }
            viz[nod]=1;
        }
    }
    for(int i=2;i<=n;++i)
        if(drum[i]==2000000000)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",drum[i]);
    fclose(f);
    fclose(g);
    return 0;
}