#include <fstream>
#include <vector>
#define N 50000
#define M 250000
#define INF 5000000

using namespace std;

vector < pair <int,int> > v[N+5];
int c[5*N+5],d[N+5],n,m;
void bellmanford(int nod)
{
    for(int i=1;i<=n;i++)
      d[i]=INF;
    d[nod]=0;
    int p,u;
    p=u=1;
    c[1]=nod;
    while(p<=u)
    {
        int x;
        x=c[p];
        p++;
        for(int i=0;i<v[x].size();i++)
        {
              int y=v[x][i].first;
              int cost=v[x][i].second;
              if(d[y]>d[x]+cost)
              {
                 d[y]=d[x]+cost;
                 c[++u]=y;
              }

        }
    }


}
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        v[a].push_back(make_pair(b,c));

    }
    for(int i=1;i<=n;i++)
      d[i]=INF;
    bellmanford(1);
    for(int i=2;i<=n;i++)
      if(d[i]==INF)
        g<<0<<" ";
      else
        g<<d[i]<<" ";
    return 0;
}